Interval Intersection in O(1) Time Complexity using C++

Given two closed intervals [A1, B1] and [A2, B2], check and return if the two intervals intersect each other.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

Two closed intervals are said to intersect if they have common numbers, i.e. that appear in both intervals.

Understanding the Problem

The core challenge of this problem is to determine if two intervals overlap. This is a common problem in computational geometry and has applications in scheduling, computer graphics, and more. A common pitfall is to overcomplicate the solution by considering all possible overlap scenarios, but a simpler approach exists.

Approach

To solve this problem, we can think about when the intervals do not intersect. Two intervals do not intersect if one is completely to the left or right of the other. Specifically, intervals [A1, B1] and [A2, B2] do not intersect if:

B1 < A2: Interval 1 ends before Interval 2 starts.
B2 < A1: Interval 2 ends before Interval 1 starts.

If neither of these conditions is true, the intervals must intersect.

Algorithm

The algorithm can be broken down into the following steps:

Check if B1 < A2 or B2 < A1.
If either condition is true, return false.
Otherwise, return true.

Code Implementation


#include <iostream>
using namespace std;

// Function to check if two intervals intersect
bool doIntervalsIntersect(int A1, int B1, int A2, int B2) {
    // Check if one interval is completely to the left of the other
    if (B1 < A2 || B2 < A1) {
        return false;
    }
    return true;
}

int main() {
    // Test cases
    cout << doIntervalsIntersect(1, 6, 3, 8) << endl; // true
    cout << doIntervalsIntersect(1, 4, 4, 6) << endl; // true
    cout << doIntervalsIntersect(1, 8, 4, 6) << endl; // true
    cout << doIntervalsIntersect(4, 6, 1, 3) << endl; // false
    return 0;
}

Complexity Analysis

The time complexity of this solution is O(1) because it involves a constant number of comparisons. The space complexity is also O(1) as no additional space is used beyond a few variables.

Edge Cases

Potential edge cases include:

Intervals that touch at a single point, e.g., [1, 4] and [4, 6]. These should be considered as intersecting.
Intervals that are exactly the same, e.g., [1, 5] and [1, 5].
Intervals where one is completely within the other, e.g., [1, 10] and [3, 7].

Testing

To test the solution comprehensively, consider the following test cases:

Intervals that overlap partially.
Intervals that touch at a single point.
Intervals that are completely separate.
Intervals that are exactly the same.
Intervals where one is completely within the other.

Thinking and Problem-Solving Tips

When approaching interval problems, it is often helpful to visualize the intervals on a number line. This can make it easier to see the relationships between the intervals and identify the conditions for intersection or non-intersection. Practice with a variety of interval problems to develop a strong intuition for these types of questions.

Conclusion

Understanding how to determine if two intervals intersect is a fundamental skill in computational geometry with many practical applications. By focusing on the conditions for non-intersection, we can derive a simple and efficient solution. Practice and visualization are key to mastering these types of problems.