Intervals

The one setup step that unlocks almost everything

Intervals arrive in whatever order the input gives them — which tells you nothing useful. Sort them by start time first, and suddenly you only ever need to compare each interval against the most recent one you've processed, instead of checking against all of them. That single sort is the setup step for nearly every interval problem you'll see.

Merging overlapping intervals

function merge(intervals) {
  if (intervals.length === 0) return []; // nothing to merge — without this guard the result would be [undefined]

  const sorted = [...intervals].sort((a, b) => a[0] - b[0]); // sort a COPY by START — enables the single left-to-right pass

  const result = [[...sorted[0]]]; // copy the first interval, so extending it never writes into the caller's data
  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];
    const last = result[result.length - 1];

    if (start <= last[1]) {
      last[1] = Math.max(last[1], end); // overlaps — extend the last merged interval
    } else {
      result.push([start, end]); // no overlap — starts a new group (a fresh copy)
    }
  }
  return result;
}

Two pitfalls hide in the shorter version, which starts with [intervals[0]] and sorts in place. On an empty input it returns [undefined], and because that first element is the caller's own inner array, extending it rewrites the input: merging [[1,3],[2,6]] would leave the caller holding [[1,6],[2,6]]. The sort would also reorder the caller's array. The guard and the copies above cost one line each and avoid both.

Meeting Rooms I: can one person attend everything?

The simplest question you can ask of a list of meetings: is there any pair that overlaps? Sort by start time. Suppose no earlier pair has clashed. Then the meetings so far follow each other in order, and the latest end among them belongs to the last one. So the next meeting clashes with something earlier exactly when it starts before the end of the one just before it, and one pass over sorted neighbours decides the whole question.

function canAttendMeetings(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] < sorted[i - 1][1]) return false; // starts before the previous one ends
  }
  return true; // back-to-back meetings, where one ends as the next starts, are allowed
}

[[0, 30], [5, 10], [15, 20]] returns false, because after sorting, [5, 10] starts at 5, before the 30 at which the first meeting ends. [[7, 10], [2, 4]] returns true: sorted, 2 to 4 ends before 7. And [[1, 2], [2, 3]] returns true: the strict < lets a meeting start at the moment the last one ends. Time is O(n log n) for the sort plus a linear pass, so the sort dominates. The sort is on a copy, so the caller's order is untouched.

Inserting a new interval into an already-sorted, non-overlapping list

function insert(intervals, newInterval) {
  const result = [];
  let i = 0;

  // 1. everything that ends before newInterval starts — keep as-is
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i++]);
  }

  // 2. everything that overlaps newInterval — merge it in
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval = [
      Math.min(newInterval[0], intervals[i][0]),
      Math.max(newInterval[1], intervals[i][1]),
    ];
    i++;
  }
  result.push(newInterval);

  // 3. everything that starts after newInterval ends — keep as-is
  while (i < intervals.length) result.push(intervals[i++]);

  return result;
}

Three clean phases instead of one tangled loop — this is a genuinely common interview shape: split the problem into "before," "during," and "after" relative to the thing you're inserting.

Interval list intersections: two sorted lists, two pointers

Two people each hand you a sorted list of busy intervals, and inside each list the intervals do not overlap. Find every time that both are busy. This is a merge, like merging two sorted arrays, and no sort is needed. Look at the current interval from each list. Their overlap, if there is one, starts at the later start and ends at the earlier end, and exists when that start is not after that end. Then advance the pointer of the interval that ends first: it cannot overlap anything further along in the other list, because everything further along starts after the interval the other pointer is on.

function intervalIntersection(first, second) {
  const result = [];
  let i = 0, j = 0;
  while (i < first.length && j < second.length) {
    const start = Math.max(first[i][0], second[j][0]); // the overlap starts at the later start
    const end = Math.min(first[i][1], second[j][1]); // and ends at the earlier end
    if (start <= end) result.push([start, end]); // a single shared point, start === end, still counts
    if (first[i][1] < second[j][1]) i++; // drop the interval that ends first: it cannot meet anything later
    else j++;
  }
  return result;
}

Dry run: first = [[0, 2], [5, 10], [13, 23], [24, 25]], second = [[1, 5], [8, 12], [15, 24], [25, 26]]

The result is [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]. Each step advances one pointer, so there are at most first.length + second.length steps: O(n + m) time, and the output is the only extra space. Three details cost people offers. The test is start <= end, not <, because two closed intervals that meet at one point, like [1, 5] and [5, 10], share that point; the problem is stated with closed intervals, and you should confirm that. The pointer to advance is the one with the smaller end, not the smaller start. And when the ends are equal, advancing either one is fine, since the next step will find no overlap for the other.

Employee free time: merge the busy intervals, read the gaps

Several employees each have a list of busy intervals. Find the periods when everybody is free, leaving out the time before anyone starts and after everyone is done. Everyone free means nobody is busy, so you can ignore which employee owns an interval: pour all the intervals into one list and sort by start. Now sweep, keeping busyUntil, the latest end seen so far. When the next interval starts after busyUntil, the stretch in between is free for everyone. This is the merge from the first section, except that you report the gaps instead of the merged blocks.

function employeeFreeTime(schedules) {
  const all = schedules.flat().sort((a, b) => a[0] - b[0]); // every busy interval of every employee
  const free = [];
  if (all.length === 0) return free;
  let busyUntil = all[0][1];
  for (let i = 1; i < all.length; i++) {
    const [start, end] = all[i];
    if (start > busyUntil) free.push([busyUntil, start]); // nobody is busy in between
    busyUntil = Math.max(busyUntil, end);
  }
  return free;
}

Dry run: [[[1, 2], [5, 6]], [[1, 3]], [[4, 10]]]

The only time everyone is free is [[3, 4]]. The line that uses Math.max is the one that matters: the interval [5, 6] sits entirely inside [4, 10], and if busyUntil were simply set to the latest interval's end, it would drop back to 6 and invent free time that is not there. With N intervals in total, sorting costs O(N log N) and the sweep is O(N). The employees' lists are already sorted, so a k-way merge with a heap would cost O(N log k) instead; the flat sort is the one to write first, and the merge is a follow-up you can offer.

Minimum number of rooms/resources needed (meeting rooms)

How many overlapping meetings exist at the same time, at once? Track starts and ends as separate sorted event streams — whenever a meeting starts before the earliest still-running meeting ends, you need another room.

function minMeetingRooms(intervals) {
  const real = intervals.filter(i => i[0] < i[1]); // a [5, 5] meeting takes no time and needs no room
  const starts = real.map(i => i[0]).sort((a, b) => a - b);
  const ends = real.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0, maxRooms = 0;
  let s = 0, e = 0;
  while (s < starts.length) {
    if (starts[s] < ends[e]) {
      rooms++;       // a meeting started before the earliest one ended
      s++;
    } else {
      rooms--;       // a meeting ended — free up a room
      e++;
    }
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

Dry run: minMeetingRooms([[0, 30], [5, 10], [15, 20]])

starts = [0, 5, 15], ends = [10, 20, 30]

rooms peaks at 2, while [0,30] and [5,10] overlap. By the time the third meeting, [15,20], starts, [5,10] has already ended and freed its room — so [15,20] reuses that one instead of needing a third. Two rooms cover all three meetings. The filter drops zero-length meetings such as [5, 5]: a tie counts as "ended first", so the end of [5, 5] would be swept before its own start, e would run past the array and the loop would never end.

This is the same idea as the sliding-window pattern from the beginner tier, applied to time instead of an array — "how many things are active at once" is a two-pointer sweep over sorted event boundaries.

A min-heap solves the same problem too: push each meeting's end time when it starts, and if the heap's minimum end time is ≤ the new meeting's start, pop it (reuse that room) instead of allocating a new one — heap size at the end is the room count. Both approaches are O(n log n); the two-pointer version above just avoids the heap's constant-factor overhead.

Meeting Rooms II with a heap, written out

The paragraph above described the heap solution in words. Here it is as code, because it is the version that generalises: the heap only needs the meetings to arrive in order of start time, one at a time, and the same shape answers "which room is free first". JavaScript has no built-in heap, so this uses a short binary min-heap of end times. The idea is to process meetings in order of start time and keep one entry per room in use, namely the time at which that room frees up. The smallest entry, the top of the heap, is the room that frees up first. If it is free by the time the new meeting starts, reuse that room, and otherwise a new room is needed. In both cases the new meeting's end time goes into the heap.

class MinHeap {
  constructor() {
    this.items = [];
  }

  get size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (a[parent] <= a[i]) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }

  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const left = 2 * i + 1, right = left + 1;
        let smallest = i;
        if (left < a.length && a[left] < a[smallest]) smallest = left;
        if (right < a.length && a[right] < a[smallest]) smallest = right;
        if (smallest === i) break;
        [a[smallest], a[i]] = [a[i], a[smallest]];
        i = smallest;
      }
    }
    return top;
  }
}

function minMeetingRoomsHeap(intervals) {
  const meetings = intervals.filter(([start, end]) => start < end).sort((a, b) => a[0] - b[0]);
  const endTimes = new MinHeap(); // one end time per room that is in use
  for (const [start, end] of meetings) {
    if (endTimes.size > 0 && endTimes.peek() <= start) {
      endTimes.pop(); // the room that frees up first is free by now: reuse it
    }
    endTimes.push(end); // this meeting occupies a room until its end
  }
  return endTimes.size;
}

Dry run: [[0, 30], [5, 10], [15, 20]]

The heap ends with 2 entries, so 2 rooms. The test is <=: a room that frees at 15 can host a meeting that starts at 15, which matches the two-array sweep above, where a tie counts as "ended first". Each of the n meetings does one push and at most one pop, each O(log n), so the time is O(n log n) and the heap holds at most as many entries as there are rooms. The heap can also tell you which room is free, not just how many, once each entry stores a room number beside its end time, which is what a follow-up such as "assign each meeting a room number" needs. The filter at the top drops zero-length meetings for the same reason as before.

Non-overlapping intervals: remove the fewest, sorting by end

Given intervals, remove as few as possible so that the rest do not overlap. Removing the fewest is the same as keeping the most, and keeping the most non-overlapping intervals is exactly the activity-selection problem from the greedy chapter: sort by end time, keep an interval whenever it starts at or after the end of the last one kept, and count the ones you skip. The sort key is what makes it work. An interval that ends earliest leaves the most room, so keeping it can never cost a later choice.

function eraseOverlapIntervals(intervals) {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]); // by END: keep whatever frees the line soonest
  let removed = 0, lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) {
      lastEnd = end; // fits after the last kept interval: keep it
    } else {
      removed++; // clashes with the kept one, which ends no later: drop this one
    }
  }
  return removed;
}

Dry run: [[1, 2], [2, 3], [3, 4], [1, 3]]

sorted by end: [1, 2], [2, 3], [1, 3], [3, 4]

One interval has to go. The comparison is >= because intervals that merely touch, like [1, 2] and [2, 3], do not overlap here. If the problem says touching counts as an overlap, the comparison becomes >; ask. Time is O(n log n), space O(1) beyond the sorted copy.

You can also sort by start, and it works if you handle a clash carefully. Walk the sorted list. When the next interval overlaps the last one you kept, you must drop one of the two, and you drop the one that ends later, because the one that ends sooner leaves more room.

function eraseOverlapByStart(intervals) {
  if (intervals.length === 0) return 0;
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]); // by START instead
  let removed = 0, lastEnd = sorted[0][1];
  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];
    if (start >= lastEnd) {
      lastEnd = end;
    } else {
      removed++; // a clash: of the two, drop the one that ends later
      lastEnd = Math.min(lastEnd, end);
    }
  }
  return removed;
}

This version returns the same counts, and it is useful to know because it shows what the sort-by-end trick buys you: with the end sort you never have to decide which of two clashing intervals to drop, since the one you already kept always ends first. The start-sorted version needs the extra Math.min on a clash, and forgetting it, so that lastEnd stays at the larger end, is the classic bug.

Remove covered intervals: sort start up, end down

An interval is covered if another one contains it completely. Count the intervals that are not covered. Sort by start ascending. Then every interval that could cover the current one comes earlier or ties on the start, and the current one is covered exactly when some earlier interval's end reaches at least as far. So keep the largest end seen so far: if the current end is bigger, the interval is not covered and it becomes the new maximum.

The tie-break is the part that is easy to get wrong. When two intervals share a start, the longer one must come first. Sorted with the longer first, the shorter one then fails the "reaches farther" test and is correctly counted as covered. If the shorter one came first, it would be counted and kept, and then the longer one would be kept too, although the longer one covers it.

function removeCoveredIntervals(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0] || b[1] - a[1]); // start up, then end DOWN
  let kept = 0, maxEnd = -Infinity;
  for (const [, end] of sorted) {
    if (end > maxEnd) { // reaches farther than everything before it: not covered
      kept++;
      maxEnd = end;
    }
  }
  return kept;
}

For [[1, 4], [3, 6], [2, 8]] the sorted order is [1, 4], [2, 8], [3, 6]. The first is kept (maxEnd = 4), the second reaches 8 and is kept, and the third reaches only 6, which is not beyond 8, so it is covered by [2, 8]. The answer is 2. For [[1, 4], [1, 6]], the sort puts [1, 6] first, and the [1, 4] is covered. Time is O(n log n). The code assumes the intervals are distinct; with exact duplicates you must say whether one copy covers the other.

Minimum arrows: a stabbing problem in the same family

Given spans on a line, shoot the fewest vertical arrows so that every span is hit, where an arrow at x hits every span with start <= x <= end. This is the "fewest points that stab every interval" problem, and the greedy chapter works it through with a proof: sort by end, shoot at the end of the first span that is not yet hit, and skip every span that starts at or before that point. In terms of this chapter, the answer is the maximum number of intervals that are pairwise disjoint when touching counts as overlapping, which is the non-overlapping count above computed with a strict comparison. The one thing to take from it here is the touching rule: for arrows, [1, 2] and [2, 3] share the point 2, so one arrow is enough, and the test for "needs a new arrow" is a strict start > arrowAt.

Sweep line: turn intervals into events

A different way to look at a list of intervals is to forget the pairs and keep only the moments something changes. Each interval gives two events: at its start the number of active things goes up, and at its end it goes down. Sort all the events by time and walk through them, keeping a running count. The count after each event is how many intervals are active at that moment, and the largest count is the answer to "how many at once". The two-pointer room count earlier is this idea with the events split into two sorted arrays.

function maxOverlapSweep(intervals) {
  const events = [];
  for (const [start, end] of intervals) {
    if (start >= end) continue;
    events.push([start, 1]);
    events.push([end, -1]);
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // at a tie, ends (-1) come before starts (+1)
  let active = 0, best = 0;
  for (const [, change] of events) {
    active += change;
    best = Math.max(best, active);
  }
  return best;
}

The tie-break is the whole subtlety. At a time where one interval ends and another starts, the end must be processed first, so that back-to-back meetings do not count as overlapping. The sort a[1] - b[1] does that, because the end event carries -1 and the start event carries +1. Flip it and [[1, 2], [2, 3]] reports 2 active at once instead of 1. If the problem treats touching as overlapping, flip the tie-break on purpose.

The events can carry weights as well as plus and minus one, which is where most sweep-line questions come from. Car Pooling asks whether a car with a given capacity can complete every trip, where a trip is [passengers, from, to] and the passengers are on board from from up to, but not including, to.

function carPooling(trips, capacity) {
  const events = [];
  for (const [passengers, from, to] of trips) {
    events.push([from, passengers]); // they get on at "from"
    events.push([to, -passengers]); // and off at "to", before anyone boards there
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // at the same stop, drop-offs come first
  let onBoard = 0;
  for (const [, change] of events) {
    onBoard += change;
    if (onBoard > capacity) return false;
  }
  return true;
}

Dry run: trips [[2, 1, 5], [3, 5, 7]] with capacity 3, then [[2, 1, 5], [3, 3, 7]] with capacity 4

In the first row, the passengers leave at stop 5 exactly as the others board, and the sort puts the drop-off first, so the count never exceeds 3. If the events were sorted with starts first, the count would reach 5 at stop 5 and the answer would be wrongly false. Sorting 2n events costs O(n log n), and the sweep is linear.

Difference arrays: many range updates, one pass

When the times are small whole numbers, you can skip the sort. Keep an array diff in which diff[t] records the change in the running total at time t. To add 5 to every position from a up to b, change two numbers instead of b - a + 1: add 5 at a, where the total steps up, and subtract 5 just past b, where it steps back down. At the end, a running sum over diff turns the steps back into the totals. This is the prefix-sum idea run in reverse, which the prefix sums chapter develops on its own. Car Pooling becomes:

function carPoolingDiff(trips, capacity) {
  let last = 0;
  for (const [, , to] of trips) last = Math.max(last, to);
  const diff = new Array(last + 1).fill(0);
  for (const [passengers, from, to] of trips) {
    diff[from] += passengers; // the count steps up at "from"
    diff[to] -= passengers; // and steps back down at "to"
  }
  let onBoard = 0;
  for (let stop = 0; stop <= last; stop++) {
    onBoard += diff[stop]; // the running sum of the steps is the count on board
    if (onBoard > capacity) return false;
  }
  return true;
}

The array is sized by the largest stop, and each trip costs two updates, so the total is O(n + maxStop). That beats the sorted events when the number of trips is large and the stops are bounded, and it loses when the times are huge or sparse: a stop at 10⁹ would need an array of 10⁹ entries, and then the sorted events are the right tool, or you compress the times first.

Corporate Flight Bookings is the same trick with inclusive ranges. Each booking is [first, last, seats] for flights numbered 1 to n, and you want the total seats booked on every flight.

function corpFlightBookings(bookings, n) {
  const diff = new Array(n + 2).fill(0); // flights are numbered 1..n; the spare slot absorbs last + 1
  for (const [first, last, seats] of bookings) {
    diff[first] += seats;
    diff[last + 1] -= seats; // the range is inclusive, so the step down is one past the end
  }
  const answer = [];
  let running = 0;
  for (let flight = 1; flight <= n; flight++) {
    running += diff[flight];
    answer.push(running);
  }
  return answer;
}

Dry run: [[1, 2, 10], [2, 3, 20], [2, 5, 25]] with n = 5

The running sum over flights 1 to 5 is 10, 55, 45, 25, 25, which is the answer. The array has n + 2 slots on purpose: a booking that ends on the last flight writes to index n + 1. Because the range is inclusive, the step down belongs at last + 1; writing it at last would remove the seats one flight too early. Time is O(n + number of bookings), against O(n × bookings) for adding to every flight in the range.

My Calendar I: booking without a double booking

Design a calendar that accepts book(start, end) for the half-open range [start, end) and refuses a booking that overlaps one already made. The heart of it is the overlap test for two half-open ranges. Two ranges overlap exactly when each one starts before the other ends: start < e && s < end. Both halves matter, because they cover the case where the new booking sits inside an old one and the case where it surrounds one.

class MyCalendar {
  constructor() {
    this.booked = [];
  }

  book(start, end) {
    for (const [s, e] of this.booked) {
      if (start < e && s < end) return false; // [start, end) and [s, e) share a moment
    }
    this.booked.push([start, end]);
    return true;
  }
}

book(10, 20) is accepted. book(15, 25) is refused, because 15 < 20 and 10 < 25. book(20, 30) is accepted: the range [10, 20) does not include 20, and the test 20 < 20 is false. Each call scans the existing bookings, so the time is O(k) for the k bookings so far, and n bookings cost O(n²) in total. That is right for small inputs. For many bookings, keep the booked ranges in a sorted structure and find the neighbours of the new range by binary search, which makes the check logarithmic, though inserting into a plain sorted array still shifts elements. The variants where overlaps are allowed up to some depth (My Calendar II and III) are the sweep line again, counting how many bookings are active.

Sort by start or by end? A table to decide

A rule of thumb that holds in this chapter: sort by start when you are building or comparing against what came before you (merging, clash checks), and by end when you are choosing which intervals to keep or which point to use (scheduling, stabbing). The touching column is the one to say out loud before coding, because the same pair of intervals is an overlap in one problem and not in the next.

Recognizing it in an unseen problem

• Input is a list of [start, end] pairs, or "meetings," "bookings," "ranges"
• "Merge," "overlap," "how many at the same time," "minimum rooms/resources"
• Almost always starts with sorting by start (or end, for the greedy scheduling case in the previous chapter) — decide which based on what the question actually asks
• If it also involves inserting one new interval into an existing sorted set, think in three phases: before, overlapping, after
• "Fewest removed" or "most kept" → sort by end and keep what fits; "fewest points or arrows to hit everything" → also sort by end
• Two already-sorted lists of intervals → two pointers, advancing whichever ends first, with no sort
• "When is everyone free" → pour every interval into one list and read the gaps behind a running maximum end
• "How many at once", "does the load ever exceed a limit" → events with plus and minus weights, ends before starts at a tie; or a difference array when the times are small whole numbers
• A booking that must not overlap earlier ones → the half-open overlap test start < e && s < end
• Before coding, ask what touching ends mean: the same pair is an overlap in one problem and not in the next