Search lands in PR-5.1 (Pagefind).
How-to Intermediate

Chapter 1 Updated

Non-Overlapping Intervals

Sort by end, greedily keep the earliest-finishing interval.

  • Full 6m
  • Revision 2m
  • Flow 1m

Problem

LeetCode #435 — one-liner.

  • Return the minimum number of intervals to remove so the remaining ones don’t overlap.

Key insight

Greedy — sort by end.

  • Activity Selection in disguise — keep the interval that finishes first, it leaves the most room.
  • Sorting by end is the key. Sorting by start loses greedy correctness ([1,100] first would block everything).
  • Every time the next interval starts before last_end, it’s the one to throw away.

Solution template

Five lines of greedy.

intervals.sort(key=lambda x: x[1])
count, last_end = 0, intervals[0][1]
for s, e in intervals[1:]:
    if s < last_end: count += 1
    else:            last_end = e

Complexity

Sort-bound and constant space.

  • Time O(n log n) — sort; scan is O(n).
  • Space O(1) — just count and last_end.

Edge cases

Three to remember.

  • Why sort by end? Sort by start picks [1, 100] first and blocks everything.
  • All identical intervals → keep 1, remove the rest.
  • No overlaps → return 0.

Comments

Comments are disabled in this environment. Set PUBLIC_GISCUS_REPO, PUBLIC_GISCUS_REPO_ID, and PUBLIC_GISCUS_CATEGORY_ID to enable.