Card 08/ 08
Recap: Intervals
Sort by start and compare with the last merged interval; walk two lists with two pointers; sweep the events to count how many at once.
Interval problems turn on order. Sorted by start, an interval can only overlap the last one merged, so merging is one pass; two sorted lists intersect by walking a pointer through each; and counting how many run at once sorts the starts and ends together and keeps a running count. Whether touching intervals overlap is a decision about the times, not the code:
| Question | Sort by | Pass | Touching intervals | Cost |
|---|---|---|---|---|
| Merge overlaps | Start | Compare with the last merged | Merge when closed | O(n log n) |
| Insert one interval | Already sorted | Before, overlapping, after | Merge when closed | O(n) |
| Intersect two lists | Already sorted | Two pointers, earlier end moves | Overlap when closed | O(n + m) |
| Most at once | Event time | Running count, or a min-heap of ends | Apart when half-open | O(n log n) |
Sorting by end is the slip to watch for: a long interval that starts early arrives last and merges into the wrong neighbour, with no error. Extending with the larger end, not the current one, keeps an interval that sits inside another from shrinking it.
← → move through sections and cards