Problem overview
The function intersect receives two closed intervals, [a1, b1] and [a2, b2], as four i32 values, and returns a bool: do the intervals share at least one number? A closed interval includes both of its ends, so [1, 4] and [4, 6] share the number 4.
Examples: [1, 6] and [3, 8] overlap on 3 to 6, so the answer is true. [1, 4] and [4, 6] only touch at 4, which still counts, so true. [1, 8] contains [4, 6], so true. [4, 6] and [1, 3] are apart, so false. The lesson asks for O(1) time and space, so a fixed number of comparisons and no loops.
Approach
Listing every way two intervals can overlap is tedious: partial overlap from either side, one inside the other, touching ends. Listing the ways they can miss each other is much shorter. They miss exactly when one lies completely to the left of the other:
- the first ends before the second starts:
b1 < a2, or - the second ends before the first starts:
b2 < a1.
If neither holds, the intervals share a number, so the answer is the negation of "one of those holds". The comparisons are strict because touching ends, as in [1, 3] and [3, 5], share the point 3 and must count as intersecting.
Step by step
- Write the two "apart" conditions:
b1 < a2andb2 < a1. - Join them with
||. The intervals are apart if either condition holds, so you need "or". - Put the combined condition in parentheses and negate it with
!. Without the parentheses,!would apply tob1 < a2alone. - Return the result in a single
returnstatement. It isfalsewhen the intervals are apart andtrueotherwise.
The solution in Rust
impl Solution {
fn intersect(a1: i32, b1: i32, a2: i32, b2: i32) -> bool {
return !(b1 < a2 || b2 < a1);
}
}
Rust details worth knowing:
- Comparisons produce a
bool.b1 < a2is an expression whose value istrueorfalse, so you can return it, combine it and negate it directly without anif. ||,&&and!. Rust uses these three symbols for or, and and not, not the words.||and&&short-circuit: ifb1 < a2is already true, the second comparison isn't evaluated.- The final expression. The function can also drop the
returnand the semicolon, leaving!(b1 < a2 || b2 < a1)as its last expression. - Equivalent form. By De Morgan's laws, the same test reads
a2 <= b1 && a1 <= b2: each interval must start no later than the other ends. Both forms always agree.
Complexity
Time: O(1). The function performs two comparisons and a negation, no matter how large the numbers are.
Space: O(1). No data is stored besides the four parameters.
Edge cases and common mistakes
- Touching ends. Using
<=in the "apart" conditions would report[1, 4]and[4, 6]as not intersecting. Closed intervals include their ends, so the comparisons must be strict. - One inside the other.
[1, 8]and[4, 6]givefalsefor both "apart" conditions, so the result istrue. No special case is needed. - Order of the two intervals. Swapping the intervals swaps the two conditions, so the result is the same either way.
[4, 6]with[1, 3]is apart throughb2 < a1. - Missing parentheses. Writing
!b1 < a2 || b2 < a1compiles but means something else:!binds tighter than<, so it applies to the integerb1. On an integer,!flips every bit instead of negating a condition, so the comparison uses a changed number. - Single point intervals.
[3, 3]and[3, 3]intersect, and[3, 3]with[4, 4]do not.
Testing
a1 = 1, b1 = 6, a2 = 3, b2 = 8givestrue.a1 = 1, b1 = 4, a2 = 4, b2 = 6givestrue.a1 = 1, b1 = 8, a2 = 4, b2 = 6givestrue.a1 = 4, b1 = 6, a2 = 1, b2 = 3givesfalse.a1 = 3, b1 = 3, a2 = 4, b2 = 4givesfalse.
