Problem overview
The method intersect receives two closed intervals, [a1, b1] and [a2, b2], as four integers. A closed interval [a, b], with a <= b, contains every number x such that a <= x <= b, both ends included. The method returns true when the two intervals share at least one number, and false when they share none.
Four cases show the possibilities:
[1, 6]and[3, 8]overlap on 3 to 6, so the answer istrue.[1, 4]and[4, 6]only touch at 4. Closed intervals include their ends, so 4 belongs to both, and the answer istrue.[1, 8]and[4, 6]: the second sits entirely inside the first, so the answer istrue.[4, 6]and[1, 3]: the second ends at 3, before the first starts at 4, so the answer isfalse.
The statement asks for O(1) time and O(1) extra space, so the answer has to come from a few comparisons, not from listing the numbers in each interval.
Approach: describe the ways to miss
Intervals can overlap in many ways: partly from the left, partly from the right, one inside the other, one equal to the other. Listing all those is tedious. Missing each other has only two ways:
- the first interval is entirely to the left of the second:
b1 < a2; - the second interval is entirely to the left of the first:
b2 < a1.
If neither holds, the intervals must share a number, so they intersect. The answer is the negation of "one of them is entirely to the left of the other".
Step by step
The lesson has one step, made of these parts:
- Write the two ways to miss:
b1 < a2andb2 < a1. - Join them with
||. Either one is enough for the intervals to be apart. Put the pair in parentheses. - Negate with
!. The negation istrueexactly when neither miss condition holds, so it is the answer. - Return it in one
returnstatement. The expression is already aBoolean, so noiforelseis needed.
The solution in Scala
class Solution {
def intersect(a1: Int, b1: Int, a2: Int, b2: Int): Boolean = {
return !(b1 < a2 || b2 < a1)
}
}
The Scala details worth knowing:
- The parentheses matter.
!binds tighter than||. Without the parentheses,!b1 < a2 || b2 < a1would try to apply!to the integerb1and fail to compile. The parentheses make!apply to the whole condition. - De Morgan's law.
!(p || q)equals!p && !q. So the same method can be written asa2 <= b1 && a1 <= b2: "the second starts no later than the first ends, and the first starts no later than the second ends". Negating<gives>=, which turns into<=when the sides are swapped. - The
returnis optional. The body's last expression is the result, so!(b1 < a2 || b2 < a1)alone would do.
Complexity
Time: O(1). The method makes two comparisons, one OR and one negation, whatever the size of the numbers. Space: O(1). No extra data is stored.
Edge cases and common mistakes
- Touching intervals.
[1, 3]and[3, 5]share the point 3. The miss conditions use a strict<, so3 < 3is false and the intervals are reported as intersecting. Using<=would wrongly reject them. - One inside the other. For
[1, 8]and[4, 6], neither8 < 4nor6 < 1holds, so the answer istrue. - Single-point intervals.
[5, 5]and[5, 5]intersect, because5 < 5is false both ways. - Argument order. The signature is
intersect(a1, b1, a2, b2), with both ends of the first interval before the second. Mixing the order up turns the check into something else. - Checking only one miss. Testing only
b1 < a2misses the case where the second interval lies entirely to the left of the first.
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.intersect(1, 2, 5, 6)givesfalse.
