Interval Intersection in O(1) Time Complexity using JavaScript

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 computer science with applications in scheduling, computational geometry, 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 or B2 < A1. If neither of these conditions is true, the intervals must intersect.

Naive Solution

A naive solution might involve checking all possible overlap scenarios, but this is unnecessary and inefficient. Instead, we can use the simpler approach described above.

Optimized Solution

The optimized solution involves a single if-statement to check the non-intersecting conditions. This approach is both time and space efficient, running in O(1) time and using O(1) extra space.

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

/**
 * Function to check if two intervals intersect
 * @param {number} A1 - Start of the first interval
 * @param {number} B1 - End of the first interval
 * @param {number} A2 - Start of the second interval
 * @param {number} B2 - End of the second interval
 * @returns {boolean} - True if intervals intersect, false otherwise
 */
function doIntervalsIntersect(A1, B1, A2, B2) {
    // Check if one interval is completely to the left of the other
    if (B1 < A2 || B2 < A1) {
        return false;
    }
    // Otherwise, they must intersect
    return true;
}

// Example usage:
console.log(doIntervalsIntersect(1, 6, 3, 8)); // true
console.log(doIntervalsIntersect(1, 4, 4, 6)); // true
console.log(doIntervalsIntersect(1, 8, 4, 6)); // true
console.log(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 values. The space complexity is also O(1) as no additional space is required beyond the input parameters.

Edge Cases

Potential edge cases include:

Intervals that just touch at the endpoints, e.g., [1, 4] and [4, 6]. These should return true.
Intervals that are completely disjoint, e.g., [1, 2] and [3, 4]. These should return false.

Testing these edge cases ensures the robustness of the solution.

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 the endpoints.

Using a testing framework like Jest can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching interval problems, consider the simplest conditions first. Visualizing the intervals on a number line can help understand their relationships. Practice with similar problems to improve problem-solving skills.

Conclusion

Understanding interval intersection is crucial for many applications. By focusing on the non-intersecting conditions, we can derive a simple and efficient solution. Practice and familiarity with such problems will enhance your problem-solving abilities.

Additional Resources

For further reading and practice, consider the following resources: