Intervals
When do two intervals conflict?
Get the overlap test exactly right, including whether touching counts, and most of this unit follows.
Key idea
Two intervals overlap when neither ends before the other starts
It is easier to say when they do not overlap: one finishes before the other begins. Everything else is an overlap.
So for intervals [a1, b1] and [a2, b2], they overlap when a1 < b2 and a2 < b1. Writing it as the negation of the simple case is far more reliable than trying to enumerate the ways two intervals can sit against each other, of which there are six.
Tip
Why writing it as a negation is safer
There are six ways two intervals can sit against each other, and enumerating them is how people end up with four-clause conditions that are wrong on one case. The non-overlap statement has only two: one finishes before the other starts, or the other way round.
Negating two clauses is far easier to check than getting six right. When a condition is getting long, try describing the opposite case and negating it.
Key idea
Touching is a decision, not a fact
Whether [1, 4] and [4, 6] conflict depends entirely on what the interval means. A meeting from 1 to 4 and another from 4 to 6 do not conflict, because the first is over when the second starts. Two closed ranges of integers that both include 4 do conflict.
Strict < treats intervals as half-open, so touching is fine. Non-strict <= treats them as closed, so touching is a conflict. Neither is right in general. Read the problem, decide, and say which you chose.
Why it works
Sorting by start makes the test local
Comparing every pair is O(n squared). Sort by start time and something useful becomes true: if an interval overlaps anything earlier, it overlaps the one immediately before it in sorted order, or an even earlier one that reaches further.
For the simplest question, does any pair conflict, sorting by start means one linear pass comparing each interval to its predecessor is enough.
Gotcha
Comparing only against the immediate predecessor is not always enough
Comparing each interval with the one directly before it is sufficient for the yes-or-no question, because a conflict with any earlier interval implies a conflict somewhere in the chain.
It is not sufficient once you need to know which intervals conflict, or to merge them. An earlier interval can reach past its neighbor, so the thing to compare against is the furthest end seen so far rather than the previous interval's end. The next lesson carries exactly that value.
Tip
Sorting a list of pairs sorts by first element
Python compares lists and tuples element by element, so sorted(intervals) orders by start and breaks ties by end, with no key function needed.
When you want a different key, say the end, sorted(intervals, key=lambda pair: pair[1]) does it. That single choice, start or end, is what separates most of the problems in this unit from each other.
The shape of every problem here
Sort by start or by end. Make one pass. Compare each interval against something you are carrying: the previous interval, the current merged block, the last end you accepted.
The problem below is the smallest version: sort by start, and check whether any interval begins before its predecessor finishes.
Predict the output: strict versus non-strict
Two overlap tests differing only in strictness, applied to intervals that touch. Type the two values separated by a space.
Meeting Rooms
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.