Intervals

Overview

Interval problems reduce to a few techniques:

• Sort by start, sweep once, Merge Intervals, Insert Interval.
• Sort by end, greedy remove overlaps, Non-overlapping Intervals.
• Sweep line over events, Meeting Rooms II (count of concurrent intervals).
• Offline query + heap / sorted structure, Minimum Interval to Include Each Query.

Problems

1. 57. Insert Interval (Medium)
2. 56. Merge Intervals (Medium)
3. 435. Non-overlapping Intervals (Medium)
4. 252. Meeting Rooms (Easy)
5. 253. Meeting Rooms II (Medium)
6. 1851. Minimum Interval to Include Each Query (Hard)

Key patterns unlocked here

• Linear merge after sort, Merge / Insert Interval.
• Sort by end + keep first, Non-overlapping Intervals (exchange argument).
• Sort + sweep / priority queue, Meeting Rooms I/II.
• Offline queries with heap, Minimum Interval to Include Each Query.