DSA & System Design
Pattern 7 of 24 · Arrays & strings · 25 min

Intervals and Sweep Line

Sort intervals by start, then merge, insert or count overlaps in a single sweep.

Spot it:meetings, bookings, rangesoverlapping intervalsminimum rooms or arrowsJavaScript you'll use: Sorting and comparators Destructuring, spread and rest Heaps and priority queues
Say it in 30 seconds
  • O(n log n)Time: the sort dominates the sweep
  • O(n)Space: output, events or heap
  • -1 before +1Order for events at the same time
Show what to say

“When I see [start, end] pairs and a question about overlap, I sort first: by start to merge or find clashes, by end to keep the most. Then one sweep answers it, and +1/-1 events or a min-heap of end times count the rooms. That is O(n log n) instead of comparing every pair.”

Trade-offs

  • Sweep line vs min-heap: both O(n log n); the sweep line is shorter for how many rooms, the heap suits assigning rooms or streams.
  • Sort by start vs by end: start merges and finds clashes; end keeps the most, since [1, 100] first would block everything.
  • Sorting vs difference array: small integer coordinates allow +1 at start, -1 at end and one prefix sum, with no O(n log n) sort.

Bring it up before they ask

Settle whether touching intervals overlap before coding ([1, 3] and [3, 5] clash with <= but not with <), and extend with Math.max because a later interval can sit inside an earlier one.

0 of 0 sections ticked
30-second answer

Sort the intervals and most problems become one sweep. To count overlaps, sweep +1/-1 events or keep a min-heap of end times: O(n log n) instead of O(n²).

When to reach for it

Spot it in the problem0 of 3

Tap the signals you can see in the problem.

Remember`[start, end]` pairsoverlaprooms

Pick your variant
  • Merge, insert or clash check

    Sort bystart

    merge intervalsmeeting rooms
  • Count overlaps

    Sort byevent time, or start plus a heap

    meeting rooms II
  • Keep the most

    Sort byend

    non-overlapping intervals
  • Two sorted lists

    Sort byalready sorted

    interval list intersections

The core idea: sorting makes overlap local

Picture meetings as bars on a calendar.

Read more · 61 words

Two overlap when each starts before the other ends. A meeting ending at 3 and one starting at 3 do not clash.

Checking every pair is O(n²). Sort by start and only neighbours matter: once an interval starts after the current group ends, every later one does too, so the group is final. Try your own intervals with Edit input:

Sort by start, then sweep: merging intervals

intervals (input order) (5×11)
1234567891011
[7,8]■■
[2,4]■■■
[10,11]■■
[1,3]■■■
[4,5]■■

In input order, intervals that overlap can be far apart ([7,8] comes first). Sort by start so overlapping intervals end up next to each other.

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (const [start, end] of intervals) {
    const last = merged.at(-1);
    if (last && start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      merged.push([start, end]);
    }
  }
  return merged;
}
All steps as text
  1. In input order, intervals that overlap can be far apart ([7,8] comes first). Sort by start so overlapping intervals end up next to each other.
  2. Sorted. Now sweep from left to right. The last interval in merged is the group still being built; everything before it is final.
  3. merged is empty, so [1,3] starts the first group.
  4. Start a new group with [1,3].
  5. [2,4] starts at 2, which is not after the open group's end (3), so they overlap.
  6. Stretch the group's end to 4: it now covers everything from 1 to 4.
  7. [4,5] starts at 4, which is not after the open group's end (4), so they overlap.
  8. Stretch the group's end to 5: it now covers everything from 1 to 5.
  9. [7,8] starts at 7, after the open group ends at 5. Every later interval starts even further right, so [1,5] is final.
  10. Start a new group with [7,8].
  11. [10,11] starts at 10, after the open group ends at 8. Every later interval starts even further right, so [7,8] is final.
  12. Start a new group with [10,11].
  13. One pass after the sort: 5 intervals merged into 3: [1,5], [7,8], [10,11].

Play with it

Drag meetings around the day. Press Run to sweep a line across it: the peak is the number of rooms.

Read more · 81 words

  1. Pin down the overlap rule

    Do [1, 3] and [3, 5] overlap? Decide before any loop.

  2. Choose the sort key

    Start to merge or find clashes, end to keep the most.

  3. Decide what the sweep remembers

    The open group, a count, or a heap of end times.

  4. Process each interval in one step

    Extend with Math.max: a later interval can sit inside an earlier one.

  5. Flush and check the edges

    Push the last open group. Test nested and back-to-back intervals.

Interactive

Meeting scheduler

Drag a meeting or its right edge. Run sweeps a line across the day.

89101112131415161718Room 1Room 2Room 3ABC10:00–12:00DEFBusy30meetings running0
Rooms needed: 0 so farBusy blocks: 3Sweep: 12 events vs 15 pair checks

Sweeping from 8:00. Nothing has started yet.

Move, resize or remove a meeting
Meeting

Templates

Template 1: sort by start, then sweep

Sort a copy by start, keep the last merged interval open, then stretch it or start a new one.

Read more · 32 words

This is Merge IntervalsMedium. With nothing to merge it answers Meeting RoomsEasy: after sorting, a clash shows between neighbours. For Insert IntervalMedium the list is already sorted, so skip the sort and walk it once.

// Template 1: sort by start, then sweep. The last interval in `merged` is the group still being built;
// an interval that starts after its end can never be reached by anything later, so the group is final.
export function mergeIntervals(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [];
  for (const [start, end] of sorted) {
    const last = merged.at(-1);
    if (last && start <= last[1]) last[1] = Math.max(last[1], end); // overlaps (or touches): stretch
    else merged.push([start, end]);                                   // a gap: start a new group
  }
  return merged;
}

// Total length covered by at least one interval: merge first, then nothing is counted twice.
export function coveredLength(intervals) {
  return mergeIntervals(intervals).reduce((sum, [s, e]) => sum + (e - s), 0);
}

Template 2: count how many overlap at once

"How many rooms?" means "how many meetings run at the busiest moment?"

Read more · 64 words

That count only changes at a start (+1) or an end (−1). Sort these events by time and keep a running sum: the sweep line. On ties put −1 first.

To know which room each meeting gets, take meetings in start order with a min-heap of end times. Reuse the room that frees first if it's free by the next start; otherwise open one.

Sweep line: the most intervals open at once

meetings [start, end) (5×9)
123456789
[1,5]■■■■
[2,6]■■■■
[4,8]■■■■
[6,9]■■■
[8,10]■■
time (10)
1
5
2
6
4
8
6
9
8
10
change (10)
+1
-1
+1
-1
+1
-1
+1
-1
+1
-1

Turn each meeting into two events: +1 when it starts, -1 when it ends. The meetings themselves no longer matter, only these moments.

function maxOverlap(intervals) {
  const events = [];
  for (const [s, e] of intervals) events.push([s, +1], [e, -1]);
  // by time; at equal times the -1 (an end) goes first
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  let open = 0, most = 0;
  for (const [time, delta] of events) {
    open += delta;
    most = Math.max(most, open);
  }
  return most;
}
All steps as text
  1. Turn each meeting into two events: +1 when it starts, -1 when it ends. The meetings themselves no longer matter, only these moments.
  2. Sort the events by time. When an end and a start share a time, the end (-1) goes first: a room freed at that moment can be reused at once.
  3. Sweep from left to right. open is how many meetings are running right now; most is the highest it has been.
  4. At time 1 a meeting starts: open = 1. That is a new high, so most = 1. The highlighted column shows the meetings running at that moment.
  5. At time 2 a meeting starts: open = 2. That is a new high, so most = 2.
  6. At time 4 a meeting starts: open = 3. That is a new high, so most = 3.
  7. At time 5 a meeting ends: open drops to 2.
  8. At time 6 a meeting ends: open drops to 1. It is handled before the start at the same time, so the two never count as overlapping.
  9. At time 6 a meeting starts: open = 2, not above the best so far (3).
  10. At time 8 a meeting ends: open drops to 1. It is handled before the start at the same time, so the two never count as overlapping.
  11. At time 8 a meeting starts: open = 2, not above the best so far (3).
  12. At time 9 a meeting ends: open drops to 1.
  13. At time 10 a meeting ends: open drops to 0.
  14. Every event is processed and open is back to 0. At most 3 meetings ran at the same time (first reached at time 4), so 3 rooms are enough.
// Template 2a: sweep line. Every interval [start, end) becomes +1 at its start and -1 at its end.
// Sorted by time (ends before starts on ties), the running sum is how many intervals are open right now.
export function maxOverlap(intervals) {
  const events = [];
  for (const [start, end] of intervals) events.push([start, +1], [end, -1]);
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // at equal times, -1 sorts before +1
  let open = 0;
  let most = 0;
  for (const [, delta] of events) {
    open += delta;
    most = Math.max(most, open);
  }
  return most;
}

Min-heap of end times: reuse the room that frees up first

meetings (input) (5)
[2,7]
[0,5]
[6,9]
[1,3]
[4,6]
ends: (empty heap)

Take the meetings in order of start time. The heap will hold one end time per room in use, smallest on top.

function minRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const ends = new MinHeap();
  for (const [start, end] of intervals) {
    if (ends.size && ends.peek() <= start) {
      ends.pop();
    }
    ends.push(end);
  }
  return ends.size;
}
All steps as text
  1. Take the meetings in order of start time. The heap will hold one end time per room in use, smallest on top.
  2. Sorted by start, and no rooms are open yet.
  3. No room is open yet, so [0,5] gets the first one. Push 5, the time this meeting's room frees up. Rooms in use: 1.
  4. [1,3] starts at 1, but even the earliest-ending room is busy until 5. Every room is busy, so this meeting needs a new one.
  5. Push 3, the time this meeting's room frees up. Rooms in use: 2.
  6. [2,7] starts at 2, but even the earliest-ending room is busy until 3. Every room is busy, so this meeting needs a new one.
  7. Push 7, the time this meeting's room frees up. Rooms in use: 3.
  8. [4,6] starts at 4. The earliest-ending room frees up at 3, which is not after 4: that room is free.
  9. Pop 3: that room is handed over to the new meeting.
  10. Push 6, the time this meeting's room frees up. Rooms in use: 3.
  11. [6,9] starts at 6. The earliest-ending room frees up at 5, which is not after 6: that room is free.
  12. Pop 5: that room is handed over to the new meeting.
  13. Push 9, the time this meeting's room frees up. Rooms in use: 3.
  14. Every meeting has a room. The heap never had to grow past 3, so 3 rooms are enough. Its size is the answer.
// A small binary min-heap of numbers (JavaScript has no built-in priority queue).
export class MinHeap {
  #a = [];
  get size() { return this.#a.length; }
  peek() { return this.#a[0]; }
  push(x) {
    const a = this.#a;
    a.push(x);
    for (let i = a.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.#a;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      for (let i = 0; ; ) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
}

// Template 2b: rooms needed for half-open meetings. Take meetings by start; the heap holds the end time of each
// busy room, so its top is the room that frees up first. Reuse it if it is free, otherwise open a new room.
export function minRooms(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const ends = new MinHeap();
  for (const [start, end] of sorted) {
    if (ends.size && ends.peek() <= start) ends.pop(); // that room is free again: hand it over
    ends.push(end);
  }
  return ends.size;
}

Template 3: keep the most, remove the fewest

Sort by end and keep every interval that starts at or after the last kept end.

Read more · 43 words

Ending first leaves the most room (Greedy).

That is Non-overlapping IntervalsMedium. "Minimum arrows to burst balloons" is the same loop.

Template 4: two sorted lists

Both lists sorted? One pointer each. Record the intersection, then advance whichever interval ends first (Two Pointers). See Interval List IntersectionsMedium.

intervals.sort((a, b) => a[1] - b[1]);       // earliest end first
let kept = 0, lastEnd = -Infinity;
for (const [start, end] of intervals) {
  if (start >= lastEnd) { kept++; lastEnd = end; }
}
// fewest removals = intervals.length - kept

Try it

try-it.js
// Edit the intervals and press Run. The functions are the templates above.
console.log(mergeIntervals([[7, 8], [2, 4], [10, 11], [1, 3], [4, 5]])); // [[1, 5], [7, 8], [10, 11]]
console.log(mergeIntervals([[1, 10], [2, 3]]));                         // [[1, 10]]  (nested: keep the max end)

const meetings = [[1, 5], [2, 6], [4, 8], [6, 9], [8, 10]];
console.log(maxOverlap(meetings), minRooms(meetings));                   // 3 3  (two ways, same answer)
console.log(maxOverlap([[1, 3], [3, 5]]));                               // 1    (back to back is fine)

Complexity and JavaScript you'll use

Complexity

Read more · 78 words
VariantTimeExtra space
Merge, clash check, keep the mostO(n log n)O(n)
Sweep line, or start order plus min-heapO(n log n)O(n)
Two sorted listsO(n + m)O(n + m)

JavaScript you'll use

JavaScript refresher: Sorting and comparators Destructuring, spread and rest Heaps and priority queues
intervals.sort((a, b) => a[0] - b[0]);              // by start; sort() alone compares "10,12" < "9,10"
const sorted = [...intervals].sort((a, b) => a[1] - b[1]); // by end, without reordering the input
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);  // by time, then -1 before +1
for (const [start, end] of sorted) { /* … */ }      // unpack each pair
const last = merged.at(-1);                          // the open group
last[1] = Math.max(last[1], end);                    // mutate it in place: it's the same array

Interview questions

Meeting rooms: sweep line or min-heap?

Both O(n log n). The sweep line is shorter for "how many?"; the heap suits assigning rooms or streams.

Intervals arrive one at a time. What changes?

Keep merged intervals in a balanced search tree by start: O(log n) per insert.

How would you find free time common to several calendars?

Merge everyone's busy intervals, then report the gaps.

The coordinates are small integers. Is there something faster than sorting?

A difference array: +1 at the start, −1 at the end, then a prefix sum. See Prefix Sums.

Check yourself

Question 1 of 3

Score 2 out of 3 or better to mark this page complete.

1. Intervals are sorted by start and you are merging. The next interval starts after the open group's end. Why is it safe to treat that group as final?

Practice problems

Solve these in the browser editor. Each runs against hidden tests; the step-by-step solution unlocks after a wrong submission.

Open these in the problem list →

In real systems

This pattern is not only for coding rounds. Here is where it does the work in a design interview.

Next: Next: linked lists, where two pointers moving at different speeds find cycles and middles.