Interval Intersection in O(1) Time Complexity using Java

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 scheduling, computational geometry, and various other fields. The key is to identify the conditions under which two intervals do not overlap, as this simplifies the logic.

Example

Consider the intervals [1, 6] and [3, 8]. These intervals intersect because they share common numbers (3, 4, 5, and 6).

Approach

To solve this problem, we need to determine when two intervals do not intersect. Two intervals do not intersect if one is completely to the left of the other. This can be expressed with the conditions:

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.

Naive Solution

A naive solution might involve checking all possible points within the intervals, but this is inefficient and unnecessary. Instead, we can use the conditions above to determine the result in constant time.

Optimized Solution

The optimized solution involves a simple conditional check:

If B1 < A2 or B2 < A1, return false.
Otherwise, return true.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Check if B1 < A2. If true, return false.
Check if B2 < A1. If true, return false.
If neither condition is true, return true.

Code Implementation

public class IntervalIntersection {
    // Method to check if two intervals intersect
    public static boolean 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; // No intersection
        }
        return true; // Intervals intersect
    }

    public static void main(String[] args) {
        // Test cases
        System.out.println(doIntervalsIntersect(1, 6, 3, 8)); // true
        System.out.println(doIntervalsIntersect(1, 4, 4, 6)); // true
        System.out.println(doIntervalsIntersect(1, 8, 4, 6)); // true
        System.out.println(doIntervalsIntersect(4, 6, 1, 3)); // false
    }
}

Complexity Analysis

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

Edge Cases

Consider the following edge cases:

Intervals that touch at a single point, e.g., [1, 4] and [4, 6]. These should intersect.
Intervals that are completely disjoint, e.g., [1, 2] and [3, 4]. These should not intersect.

Testing

To test the solution comprehensively, consider a variety of test cases:

Intervals that overlap partially.
Intervals that overlap completely.
Intervals that do not overlap at all.
Intervals that touch at a single point.

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.

Conclusion

Understanding interval intersection is a fundamental problem with applications in many fields. By focusing on the conditions for non-intersection, we can develop an efficient solution that runs in constant time.