Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Sliding Window
  • Two Pointers
  • Prefix Sum & Hash Map
  • Cyclic Sort
  • Merge Intervals
  • Monotonic Stack
Learn/Data Structures & Algorithms/Arrays & Strings

Merge Intervals

7 min Beginner 8 steps

Sort by start, then merge or insert in one sweep.

Intervals
1
Overlaps
0
Goal
merge them
05101520#1[1, 3]
normal slow / failed marker
In this lessonStep 1 of 8
  1. The problem
  2. Six cases
  3. One test
  4. Merge run
  5. Keep max
  6. Insert
  7. Why sort
  8. Recap
Step 1 / 8problem

Overlapping intervals

Merge [[1, 3], [2, 6], [8, 10], [15, 18]] so that no two intervals overlap.

Keywords like overlap, merge, schedule, meeting rooms or conflicts all point at this pattern.

Key idea

Input is a list of [start, end] pairs and the question is about collisions: think merge intervals.

←→ step·R replay·Space pause

You'll learn

  • Name the six ways two intervals relate
  • Reduce every case to one comparison after sorting by start
  • Merge overlapping intervals in one sweep
  • Insert an interval in three phases without sorting
  • Explain why the sort is not optional
Read the full notesArrays and Linked Lists, 5