Problem overview
The method Intersect takes the endpoints of two closed intervals, [A1, B1] and [A2, B2], and returns a bool: true when the intervals share at least one number, false otherwise. "Closed" means that both endpoints belong to the interval, so [1, 4] contains 1, 4 and everything between.
Take the examples. [1, 6] and [3, 8] share the numbers 3 to 6, so the answer is true. [1, 4] and [4, 6] share exactly one number, 4, so the answer is true. [1, 8] contains [4, 6] completely, so the answer is true. [4, 6] and [1, 3] share nothing, so the answer is false.
The lesson asks for O(1) time and space, which means no loops: a fixed number of comparisons.
Approach: count the ways to miss
Intervals can overlap in many ways: partly from the left, partly from the right, or with one inside the other. Listing all of them is tedious. Intervals can miss each other in only two ways, so describe those and negate:
- The first interval ends before the second begins:
B1 < A2. - The second interval ends before the first begins:
B2 < A1.
If neither of those holds, the intervals must overlap. This works because an interval is a single unbroken stretch: if one doesn't lie entirely to the left of the other, and doesn't lie entirely to the right, the two stretches must share a point.
Step by step
- Write the "no overlap" condition. It is
B1 < A2 || B2 < A1. Either one is enough to separate the intervals, so they are joined with||. - Use strict comparisons. The test is
<, not<=. Intervals like[1, 4]and[4, 6]touch at 4, and since both are closed, they do intersect. HereB1 < A2is4 < 4, which is false. - Negate the condition. Put the whole expression in parentheses and add
!in front. The method returnsfalseif either "miss" condition holds andtrueotherwise. This takes a singlereturnstatement.
The solution in C#
class Solution {
public bool Intersect(int A1, int B1, int A2, int B2) {
return ! (B1 < A2 || B2 < A1);
}
}
Some details about this code:
- A
boolexpression can be returned directly. There is no need forif (...) { return false; } return true;, because the expression already evaluates to the answer. - The parentheses matter.
!applies to what comes right after it. Without the parentheses, it wouldn't cover the whole condition, and the code would fail to compile, since!can't be applied to anint. - Parameter names. The lesson uses capitalised parameter names such as
A1andB1. C# allows that, and they must be spelled exactly as in the method signature. - The equivalent form. Negating the condition with De Morgan's laws gives
B1 >= A2 && B2 >= A1. This version says "each interval ends at or after the start of the other", and it returns the same answers.
Complexity
Time: O(1). The method compares four integers in a fixed number of steps, whatever their values. The interval can be huge, but nothing loops over its numbers.
Space: O(1). No collections or extra variables are created.
Edge cases and common mistakes
- Touching intervals.
[1, 4]and[4, 6]intersect. WritingB1 <= A2as a miss condition would wrongly reportfalse. - One interval inside another.
[1, 8]and[4, 6]:8 < 4is false and6 < 1is false, so the result istrue. - Argument order. The method works the same when the intervals are swapped, because the two miss conditions are mirror images of each other. In the fourth example,
B2 < A1is3 < 4, which is true, so the result isfalse. - Single-point intervals.
[5, 5]and[5, 5]intersect, and the formula agrees: neither5 < 5is true. - Using
&&in the miss condition. Intervals miss each other if either condition holds. Joining the conditions with&&would require both, which is impossible for valid intervals.
Testing
Intersect(1, 6, 3, 8)givestrue.Intersect(1, 4, 4, 6)givestrue.Intersect(1, 8, 4, 6)givestrue.Intersect(4, 6, 1, 3)givesfalse.