TRT
Sign in

Advanced · Module 14 · Lesson 4 of 4

Intervals and sweeping

Sort intervals by start and most interval problems become a single pass: merging overlaps, inserting a new interval, or sweeping through start and end events to count how many intervals overlap at once.

Pro — members onlyAbout 14 minutes

By the end you can

  • Test two intervals for overlap, and merge overlapping intervals after sorting by start
  • Count the maximum number of overlapping intervals with a sweep over start and end events
  • Handle the boundary cases: touching intervals, equal times and half-open ranges

Builds on Prefix sums, Stability and what libraries use.

01 · A question first

A calendar holds 10,000 meetings. How many rooms are needed so that no two overlapping meetings share a room? Comparing every pair of meetings tells you which ones overlap, but not the answer. Sorting their start and end times and walking through them once does. What are you counting as you walk?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Intervals
  • Sort by start
  • Sweeping
  • Sweeping in other problems
  • Free time across calendars
  • The end of Core
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeMerge intervalsMerge all overlapping intervals after sorting them by start, in one pass.Practice · medium · LeetCodeInsert intervalInsert a new interval into a sorted, non-overlapping list, merging where needed, in O(n).Practice · hard · LeetCodeMinimum interval to include each queryFor each query point, find the length of the shortest interval containing it, by sweeping sorted queries and keeping a heap of active intervals.

Asked in interviews

Something wrong with this lesson? Report a problem