Problem Statement
Non-overlapping Intervals
You are given a list of intervals. An interval is just a start time and an end time, like [1,3] meaning something that runs from 1 to 3. Two intervals overlap when they share part of the same time, the way two meetings that run at the same time clash. Your job is to remove as few intervals as possible so the ones left over never overlap. The answer you return is the count of intervals you removed. The trick is to sort the intervals by their end time, then walk through them and greedily keep the ones that fit, counting the ones you have to throw away.
Signals to notice
Brute force first
Try all subsets of non-overlapping intervals. Exponential. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Sort by end time. Greedily keep intervals whose start ≥ previous end. Count removals = total - kept., after sorting once and scanning greedily. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on intervals=[[1,2],[2,3],[3,4],[1,3]]
sort by end (stable) -> [[1,2],[2,3],[1,3],[3,4]]; count=0, prevEnd=-inf [1,2]: start 1 >= -inf -> keep; prevEnd=2 [2,3]: start 2 >= 2 -> keep; prevEnd=3 [1,3]: start 1 < 3 -> remove; count=1 [3,4]: start 3 >= 3 -> keep; prevEnd=4 loop ends; return count = 1
What must stay true
Sorting by end time and always keeping the interval that ends earliest maximizes room for future intervals. An interval that ends later can only block more, never help. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
sort intervals by end time ascending
count = 0; prevEnd = -infinity
for [start, end] in intervals:
if start >= prevEnd: prevEnd = end # keep
else: count += 1 # remove
return countPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Sorting by start time instead of end time — start sorting doesn't guarantee optimal packing. End sorting is the classic activity selection insight. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.