Interval Scheduling Visualization for Coding Interviews
Earliest-finish-first greedy; maximize non-overlapping intervals.
Concept
Interval Scheduling Maximization asks: given a set of intervals each with a start and finish time, pick the largest subset of mutually non-overlapping intervals. It is a textbook greedy problem whose optimal substructure is not obvious at first glance — sorting by earliest finish time and repeatedly picking the first interval that does not conflict with the last picked one is provably optimal. The same pattern underlies meeting-room scheduling, CPU job scheduling, taxi dispatch over time windows, and ad slot packing. Variants include weighted interval scheduling (maximize total weight, solvable only by DP because greedy fails), minimum number of classrooms (pick fewest rooms to schedule all intervals), and interval covering. This widget focuses on the unweighted greedy version that is elegant, fast, and asymptotically optimal at O(n log n).
How it works
Sort the intervals by their finish times in ascending order. Pick the interval with the earliest finish time, call its finish f. Walk through the remaining intervals in order and greedily select the next interval whose start is >= f, then update f to its finish. Repeat until the list is exhausted. The proof of optimality is an exchange argument: any optimal solution's earliest-finishing interval can be swapped for the one we picked without conflicts or loss of count, so greedy makes a safe first choice. By induction, greedy matches some optimal solution. The counterintuitive part is that sorting by start time or by duration both fail — 'earliest finish' is the correct greedy criterion because it leaves the most room for subsequent picks. Complexity is dominated by the sort at O(n log n), followed by a single O(n) greedy pass. Handling of touching intervals (one ends at t, another starts at t) depends on whether touching counts as overlap — the standard convention treats them as non-overlapping, which matches physical schedules where a 10am-11am meeting is compatible with an 11am-12pm meeting.
Implementation
import java.util.Arrays;
import java.util.Comparator;
public final class Intervals {
private Intervals() {}
public static int maxNonOverlapping(int[][] intervals) {
if (intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int count = 1;
int lastFinish = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= lastFinish) {
count++;
lastFinish = intervals[i][1];
}
}
return count;
}
public static int[][] selectNonOverlapping(int[][] intervals) {
if (intervals == null || intervals.length == 0) return new int[0][];
int[][] sorted = intervals.clone();
Arrays.sort(sorted, Comparator.comparingInt(a -> a[1]));
int[][] chosen = new int[sorted.length][];
int idx = 0;
chosen[idx++] = sorted[0];
int lastFinish = sorted[0][1];
for (int i = 1; i < sorted.length; i++) {
if (sorted[i][0] >= lastFinish) {
chosen[idx++] = sorted[i];
lastFinish = sorted[i][1];
}
}
return Arrays.copyOf(chosen, idx);
}
public static int minRoomsRequired(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0, maxRooms = 0, j = 0;
for (int i = 0; i < n; i++) {
if (starts[i] < ends[j]) rooms++;
else { j++; }
if (rooms > maxRooms) maxRooms = rooms;
}
return maxRooms;
}
}
Complexity
- Time:
O(n log n) - Space:
O(1) beyond the sort - Sort key:
Finish time ascending
Common pitfalls
- Sorting by start time instead of finish time — greedy becomes suboptimal.
- Treating touching intervals (end == next start) as overlapping when convention says otherwise.
- Applying this greedy to weighted interval scheduling — weighted variant requires DP with binary search.
- Mutating the caller's intervals array via Arrays.sort — clone first if needed.
- Forgetting to handle the empty input — return 0 rather than throwing.
Key design decisions & trade-offs
- Greedy vs DP — Chosen: Greedy for unweighted, DP for weighted. Weighted interval scheduling breaks the greedy; O(n log n) DP with binary search solves it.
- Sort by finish vs start — Chosen: Finish time. Provably optimal; start-time sort fails on simple counterexamples.
- Min rooms vs max selected — Chosen: Different problems, different algorithms. Min rooms uses a sweep of starts and ends; max selected uses greedy pick.
Practice problems
Interview follow-ups
- Implement weighted interval scheduling using DP with binary search for predecessor intervals.
- Solve the minimum number of meeting rooms required problem.
- Extend to find the maximum overlap depth at any time.
- Build an interval tree for efficient overlap queries.
Why it matters
Interval Scheduling is a core part of the Greedy & Backtracking toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".