Interval Scheduling: The Complete Guide with Examples
Interval scheduling is the pattern you reach for when a problem hands you a list of start and end times and asks for the maximum set of non-overlapping tasks, or the fewest resources needed to host them all. It appears in interviews in many disguises. Meetings in a room, courses with deadlines, rides in a car. The core skill is the same every time: sort the intervals, then apply one decision rule in a single pass.
Definition: an interval is a pair of times, [start, end]. Interval scheduling problems ask you to reason about a whole collection of these pairs. Which ones overlap, which ones can be selected together, and how many resources are needed to host them all. Unweighted problems yield to a greedy algorithm. When each interval carries a value, the answer needs dynamic programming.
Real-World Analogy
Think of a single room you can book for the day. Requests arrive, each with a start and end time, and you want to fit as many as possible. If you accept a request that runs from 9am to 5pm, the day is gone. If you accept the 9am to 10am slot instead, the rest of the day stays open. The rule that guarantees the most bookings is to always take the request that ends earliest among the ones that have not started yet. A short meeting that fits now never hurts, because it frees the room sooner than any other request that overlaps it.
Visual Explanation
The greedy algorithm for maximum non-overlapping intervals is short enough to hold in your head. Sort by end time, then walk the list once. Take an interval when it starts at or after the last taken interval’s end, otherwise skip it.
graph TD
A["Sort intervals by end time"] --> B["Pick the first interval and record its end"]
B --> C{"Any intervals left?"}
C -->|"Yes"| D{"Does it start at or after the last end?"}
D -->|"Yes"| E["Select it and record its end"]
D -->|"No"| F["Skip it and keep the last end"]
E --> C
F --> C
C -->|"No"| G["The selected set is the maximum"]
Notice that the decision only ever looks at the last accepted end. Everything earlier is already settled, and a skipped interval ends later than the accepted interval that blocked it, so it can never fit later on. That single fact is why one pass after the sort is enough.
When to Use This Pattern
- The input is a list of intervals with start and end times, and the question involves overlap: which ones conflict, which form the largest non-overlapping set, or how many must be removed to separate them.
- You allocate shared resources like rooms, machines, or staff to time blocks, and you want the minimum number required.
- The problem rewards an earliest-finish-first greedy choice, which is optimal whenever the intervals carry no values.
- Sorting the intervals once makes overlap easy to check, because after a sort by start time, conflicts only happen between neighboring intervals.
- A variant adds a value to each interval and asks for the maximum total value, which is the weighted case that needs dynamic programming.
Complexity Analysis
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Activity selection (greedy) | O(N log N) | O(1) | The sort dominates; selection is one pass |
| Merge intervals | O(N log N) | O(N) | The result list can hold all N intervals |
| Minimum meeting rooms (sweep) | O(N log N) | O(N) | Two sorted arrays of length N |
| Weighted interval scheduling | O(N log N) | O(N) | Binary search per interval; naive DP is O(N^2) |
Every variant starts with a sort, which costs
Common Mistakes
Sorting by the wrong endpoint. For selection problems, sort by end time. For merge problems, sort by start time. Sorting by start for activity selection breaks the greedy rule, because a long interval that starts early gets picked and then blocks several short intervals that start slightly later. The greedy proof depends on the earliest-finishing interval being considered first. To catch this during practice, check the first interval after sorting. For a selection problem it should be the earliest-finishing one, not the earliest-starting one.
Getting the overlap boundary wrong. Whether [1, 4] and [4, 6] conflict depends on the problem’s semantics, and LeetCode problems disagree with each other here. Merge Intervals treats them as overlapping and merges them, so the check is start <= lastEnd. Non-overlapping Intervals and Meeting Rooms treat them as compatible, so the check is start < lastEnd. Copying one problem’s comparison into another changes the answer exactly on this edge case. Test an input where one interval ends precisely when another starts before you trust the comparison.
Moving the last end when an interval is rejected. In activity selection, a skipped interval must not update the last end. The rejected interval is not part of the schedule, so it cannot block later intervals. If you update the last end anyway, intervals that actually fit after the kept one get rejected. Trace [2,3], [3,4], [1,5], [4,6] by hand. The correct answer keeps three intervals. The buggy version rejects [4,6] and keeps only two.
Fumbling the room sweep pointer. In the minimum-rooms problem, each start is matched against the earliest available end. A new room opens only when start < ends[endIdx]. Two common bugs are using <=, which opens a spare room for meetings that merely touch, and advancing the end pointer past the earliest free room. Both overcount. Walk the sweep with starts 0, 5, 15 and ends 10, 20, 30 to see where each bug first miscounts.
Related Patterns
- Greedy Algorithms . Activity selection is the canonical greedy problem, and the earliest-finish-first rule is where the exchange-argument proof is usually taught.
- Heap / Priority Queue . Two interval problems need a heap on top of the sort: Meeting Rooms II tracks the earliest freed room, and Course Schedule III drops the longest course when a deadline is missed.
- Two Pointers . The room sweep merges two sorted timelines with two pointers walking forward, which is the same merge mechanics as classic two-pointer problems.
Next Steps
Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.