AI Hints
Home›DSA in Python Tutorial›Counting Sort and Practice
DSA in Python · Lesson 59 of 132

Practice: Merge Intervals

Sort first, then sweep.

⏱ 2 min read▶ Video at 1:08:55🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A calendar has meetings from one to three, two to six, eight to ten, and nine to twelve. Some overlap. Merge the overlapping ones, so you can see when you're really busy. Pause. What would make this easy?

Practice: Merge Intervals
From the video: Practice: Merge Intervals
  • Meetings that overlap
  • Merge them
  • What makes it easy?

Sort, then sweep

Sort the meetings by start time. Then sweep through them. If a meeting starts before the last merged one ends, they overlap, so we stretch the end. Otherwise, it starts a new block. Run it. One to six, and eight to twelve. Sorting is O of N log N, and the sweep is O of N.

intervals.pypython
def merge_intervals(meetings):
    meetings.sort(key=lambda m: m[0])
    merged = [meetings[0]]
    for start, end in meetings[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[8, 10], [1, 3], [9, 12], [2, 6]]))
Output
[[1, 6], [8, 12]]

Sorting as step one

Many tricky problems become simple once the data is sorted. Overlapping meetings, finding pairs, removing duplicates, and finding gaps. If a problem feels hard, ask yourself, would it be easier if this was sorted? The answer is often yes.

keyvalue
Overlapssort by start
Pairssort, then two pointers
Duplicatessort, compare neighbours
Askwould sorted help?

Summary

Sort by start time, then sweep and merge overlaps. Sorting first turned a messy problem into one simple pass. Next, a sorting quiz.

Key takeaways
  • Sort by start
  • Overlap? Stretch the end
  • O(n log n)
Next up: Sorting Quiz — test yourself