Non-overlapping Intervals

Non-overlapping Intervals

What is this problem about?

The Non-overlapping Intervals problem gives you a list of intervals and asks for the minimum number of intervals to remove so that the remaining intervals are non-overlapping. This Non-overlapping Intervals coding problem is the classic greedy interval scheduling problem, equivalent to finding the maximum number of non-overlapping intervals.

Why is this asked in interviews?

J.P. Morgan, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and many others ask this because it's the canonical greedy interval scheduling problem. Solving it reveals whether candidates know the "earliest deadline first" greedy strategy — the fundamental insight for interval selection. The array, sorting, greedy, and dynamic programming interview pattern is the cornerstone here.

Algorithmic pattern used

Sort by end time + greedy selection. Sort intervals by their end time. Greedily select intervals that don't overlap with the last selected: iterate through, keeping a lastEnd pointer. If the current interval starts ≥ lastEnd, select it (update lastEnd). Otherwise, it overlaps — skip it (count it as removed). Answer = total intervals - selected intervals.

Example explanation

Intervals: [[1,2],[2,3],[3,4],[1,3]]. Sort by end: [[1,2],[2,3],[1,3],[3,4]].

• Select [1,2]: lastEnd=2. Count=1.
• [2,3]: start=2 ≥ lastEnd=2 → select. lastEnd=3. Count=2.
• [1,3]: start=1 < lastEnd=3 → skip (remove).
• [3,4]: start=3 ≥ lastEnd=3 → select. Count=3. Selected=3, removed=4-3=1.

Common mistakes candidates make

• Sorting by start time instead of end time (gives wrong greedy selection).
• Counting selected intervals as the answer instead of removed intervals.
• Using DP O(n²) when greedy O(n log n) is optimal.
• Boundary confusion: start < lastEnd (overlapping) vs start >= lastEnd (non-overlapping).

Interview preparation tip

The "earliest deadline first" greedy for interval scheduling is one of the most important algorithms in all of computer science. Memorize: sort by end time, greedily keep intervals that start after the last selected ends. The answer = total - kept. This same pattern solves "minimum meeting rooms needed" (sort starts and ends, two pointers) and "activity selection." Non-overlapping Intervals is the first problem to master when studying interval greedy algorithms.