DSA for Interviews, From Zero

Part 12 · Lesson 48 · read

Interval Problems

Sort by start time, then merge, insert and count overlapping intervals.

On this page

  1. What is an interval?
  2. When do two intervals overlap?
  3. Sort first
  4. Merge intervals
  5. Traced: merging
  6. Insert an interval
  7. Remove the fewest: sort by end
  8. Minimum arrows
  9. Meeting rooms I and II
  10. Intersections of two lists
  11. Practice questions (7)
  12. Make it stick
  13. What's next

What is an interval?

An interval is a part of a number line with a start and an end. Examples: a meeting from 9 to 10, a balloon spanning 3 to 7 on a wall, or a booking from day 5 to day 8. In code, we store one as an array with two items: [start, end]. A problem gives us a list of them: [[1, 3], [2, 6], [8, 10]].

Interval problems ask questions like these. Which of them overlap (share some of the same space)? Combine the overlapping ones. How many can I keep without any overlap? How many things happen at the same time? They all use the trick from the last lesson: sort by the right key, then scan once.

When do two intervals overlap?

Draw two intervals on a line. They overlap when neither one is completely to the left of the other. Another way to say it: each one starts before the other one ends. For a = [s1, e1] and b = [s2, e2]:

JavaScript
// Two intervals [s1, e1] and [s2, e2] (both ends included) overlap// exactly when each one starts before the other one ends.function overlaps(a, b) {  return a[0] <= b[1] && b[0] <= a[1];}console.log(overlaps([1, 3], [5, 8])); // falseconsole.log(overlaps([1, 5], [3, 8])); // trueconsole.log(overlaps([1, 8], [3, 5])); // true   (one inside the other)console.log(overlaps([1, 4], [4, 8])); // true   (they share the point 4)
Dry run · intervals drawn on a line (positions 0 to 9, # = covered)
CaseabOverlap?
apart[1,3] .###......[5,8] .....####.no
partial[1,5] .#####....[3,8] ...######.yes
inside[1,8] .########.[3,5] ...###....yes
touching[1,4] .####.....[4,8] ....#####.yes
reversed, apart[6,8] ......###.[0,3] ####......no

Each row shows the two intervals one above the other. When you are not sure about a condition, draw the two extreme cases: fully apart, and one inside the other.

Touching: is it an overlap?
Whether [1, 4] and [4, 8] overlap depends on the problem. When you merge ranges, they share the point 4, so they merge (use <=). For meetings, one that ends at 4 and the next that starts at 4 do not clash (use <). Read the problem carefully and test the touching case.

Sort first

If the intervals are in random order, any one of them could overlap any other. That needs n² comparisons (about n times n). After sorting by start, an interval can only overlap the ones right before it. So one pass from left to right is enough. Sorting costs O(n log n), and that is the cost of the whole solution.

Merge intervals

Merge means: combine all overlapping intervals, so that you have as few intervals as possible. Sort by start, and keep a list of merged results. Look at each interval. If it starts at or before the end of the last merged interval, stretch that one. Its new end is the larger of the two ends, because the new interval may sit completely inside the old one. Otherwise there is a gap, so start a new interval.

JavaScript
function merge(intervals) {  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);   // by start  const merged = [[...sorted[0]]];  for (let i = 1; i < sorted.length; i++) {    const last = merged[merged.length - 1];    if (sorted[i][0] <= last[1]) {      last[1] = Math.max(last[1], sorted[i][1]);   // overlap: make the last interval longer    } else {      merged.push([...sorted[i]]);                  // gap: start a new interval    }  }  return merged;}console.log(merge([[1, 3], [8, 10], [2, 6], [15, 18]])); // [[1, 6], [8, 10], [15, 18]]console.log(merge([[1, 4], [4, 5]]));                    // [[1, 5]]console.log(merge([[1, 10], [2, 3], [4, 5]]));           // [[1, 10]]

Traced: merging

step 1 / 10
Set up
intervals as given

The intervals come in any order. So two intervals that are next to each other in the list may not be next to each other on the number line.

▶intervals.sort((a, b) => a[0] - b[0]);2const merged = [[...intervals[0]]];3for (let i = 1; i < intervals.length; i++) {4  const last = merged[merged.length - 1];5  if (intervals[i][0] <= last[1]) {6    last[1] = Math.max(last[1], intervals[i][1]);7  } else {8    merged.push([...intervals[i]]);9  }10}11console.log(merged);
Variables
intervals[[1, 3], [8, 10], [2, 6], [15, 18]]
Console
(nothing printed yet)
After sorting, [1,3] and [2,6] overlap and become [1,6]. [8,10] and [15,18] each start after the previous end, so they stay separate. · interactive

The time is O(n log n) for the sort, plus O(n) for the scan. The space is O(n) for the result.

Insert an interval

You get a list that is already sorted and has no overlaps. You also get one new interval. Put it in, and merge whatever it touches. The list is already sorted, so you do not need to sort again. The new interval meets the list in three phases.

  1. Copy every interval that ends before the new one starts.
  2. Take in every interval that starts at or before the end of the new one. Stretch the new one to cover them.
  3. Copy the rest.
JavaScript
function insert(intervals, newInterval) {  const result = [];  let i = 0;  const n = intervals.length;  // 1. copy everything that ends before the new interval starts  while (i < n && intervals[i][1] < newInterval[0]) result.push(intervals[i++]);  // 2. everything that overlaps: take it into the new interval  let [start, end] = newInterval;  while (i < n && intervals[i][0] <= end) {    start = Math.min(start, intervals[i][0]);    end = Math.max(end, intervals[i][1]);    i++;  }  result.push([start, end]);  // 3. copy everything that starts after the new interval ends  while (i < n) result.push(intervals[i++]);  return result;}console.log(insert([[1, 3], [6, 9]], [2, 5]));                              // [[1, 5], [6, 9]]console.log(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]));    // [[1, 2], [3, 10], [12, 16]]console.log(insert([], [5, 7]));                                            // [[5, 7]]

This is O(n), because each interval is handled exactly once.

Remove the fewest: sort by end

Non-overlapping intervals: remove as few intervals as you can, so that the rest do not overlap. Turn it around: keep as many as you can. That is the activity selection problem from lesson 47, so the rule is the same. Sort by end. Keep an interval whenever it starts at or after the end of the last one you kept. The interval that ends first leaves the most room, and that is what the exchange argument needs. Sorting by start would fail on [[1, 100], [2, 3], [4, 5]]. It would keep the long one first and lose the other two.

JavaScript
// Fewest intervals to remove so the rest do not overlap.// Same as: keep as many as possible (activity selection), then take that away from the total.function eraseOverlapIntervals(intervals) {  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);   // by END  let kept = 0;  let lastEnd = -Infinity;  for (const [start, end] of sorted) {    if (start >= lastEnd) {          // touching is fine here: [1,2] and [2,3] do not overlap      kept++;      lastEnd = end;    }  }  return intervals.length - kept;}console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])); // 1console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]));         // 2console.log(eraseOverlapIntervals([[1, 2], [2, 3]]));                 // 0

Minimum arrows

Balloons are intervals along the x-axis (the line going left to right). An arrow shot straight up at position x bursts every balloon with start <= x <= end. Find the fewest arrows. It is the same sort-then-scan idea again. Sort by end. Shoot at the end of the first balloon. This is as far right as possible while still hitting it, so it catches the most later balloons. Skip every balloon that this arrow also hits. Then shoot again at the first balloon it misses. The test is start > arrowAt. It is strict, because balloons that only touch can share one arrow.

JavaScript
// Balloons are intervals on a line. One arrow at x bursts every balloon with start <= x <= end.function findMinArrowShots(points) {  const sorted = [...points].sort((a, b) => a[1] - b[1]);   // by END  let arrows = 0;  let arrowAt = -Infinity;  for (const [start, end] of sorted) {    if (start > arrowAt) {           // the last arrow does not hit this balloon      arrows++;      arrowAt = end;                 // shoot as far right as possible and still hit it    }  }  return arrows;}console.log(findMinArrowShots([[10, 16], [2, 8], [1, 6], [7, 12]])); // 2console.log(findMinArrowShots([[1, 2], [3, 4], [5, 6], [7, 8]]));    // 4console.log(findMinArrowShots([[1, 2], [2, 3], [3, 4], [4, 5]]));    // 2

Meeting rooms I and II

Meeting rooms I: can one person attend every meeting? Sort by start. If any meeting starts before the previous one has ended, the answer is no.

Meeting rooms II: what is the fewest rooms you need? Another way to ask: what is the largest number of meetings at the same moment? A classic answer uses a min-heap (lesson 46) of end times. But JavaScript has no built-in heap, so here is a neat trick that needs only sorting. Sort the starts and the ends as two separate lists. Walk through the starts in order. If a meeting starts before the earliest end that is still waiting, nobody has left yet, so you need a new room. Otherwise someone just left. Reuse their room by moving past that end.

JavaScript
// Meeting rooms I: can one person attend all meetings?function canAttendMeetings(meetings) {  const sorted = [...meetings].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;   // it starts before the previous one ends  }  return true;}// Meeting rooms II: the fewest rooms needed. Sort starts and ends SEPARATELY.function minMeetingRooms(meetings) {  const starts = meetings.map((m) => m[0]).sort((a, b) => a - b);  const ends = meetings.map((m) => m[1]).sort((a, b) => a - b);  let rooms = 0;  let e = 0;                                // the earliest meeting that has not ended yet  for (let s = 0; s < starts.length; s++) {    if (starts[s] < ends[e]) rooms++;       // nobody has left yet, so we need one more room    else e++;                               // someone just left, so reuse their room  }  return rooms;}console.log(canAttendMeetings([[0, 30], [5, 10], [15, 20]])); // falseconsole.log(canAttendMeetings([[7, 10], [2, 4]]));            // trueconsole.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]]));   // 2console.log(minMeetingRooms([[7, 10], [2, 4]]));              // 1console.log(minMeetingRooms([[1, 5], [5, 9], [9, 12]]));      // 1   (back to back is fine)
Premium questions
On LeetCode, Meeting Rooms (252) and Meeting Rooms II (253) are only for paying members. The practice section below writes them out in full, so you can solve them without an account.

Intersections of two lists

You get two lists of intervals. Each list is sorted and has no overlaps inside it. List the places where an interval from one list overlaps an interval from the other. Use two pointers (two markers that move along the lists). The overlap of the pair under the pointers, if there is one, goes from the later start to the earlier end. Then move the pointer whose interval ends first. That interval cannot overlap anything later in the other list.

JavaScript
// Two lists of sorted, non-overlapping intervals. Return where they overlap.function intervalIntersection(A, B) {  const result = [];  let i = 0, j = 0;  while (i < A.length && j < B.length) {    const lo = Math.max(A[i][0], B[j][0]);       // the later start    const hi = Math.min(A[i][1], B[j][1]);       // the earlier end    if (lo <= hi) result.push([lo, hi]);         // there is a real overlap    if (A[i][1] < B[j][1]) i++; else j++;        // move past the one that ends first, because it cannot overlap anything later  }  return result;}console.log(intervalIntersection([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]]));// [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]console.log(intervalIntersection([[1, 3], [5, 9]], []));  // []

Practice questions

Before you write code, decide two things. What will you sort by? Do touching intervals count as overlapping?

Q1Merge intervalsMedium

You get an array of intervals [start, end]. Merge all overlapping intervals. Return the intervals that do not overlap and cover the same ranges.

Example 1
Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: [1,3] and [2,6] overlap and become [1,6].
Example 2
Input: [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: They touch at 4, and touching counts as overlapping.
Stuck? Open one hint at a time
Hint 1
The intervals can come in any order. How does sorting by start help you?
Hint 2
Compare each interval only with the last merged one. The new end is the larger of the two ends.
Show all 2 solutions with explanations
Approach 1Brute force: keep merging until nothing changes
The idea

Repeat this: find any two intervals that overlap and replace them with one interval that covers both. Then start over. Stop when a full pass finds no overlap.

JavaScript
function merge(intervals) {  let list = intervals.map((x) => [...x]);  let changed = true;  while (changed) {    changed = false;    outer: for (let i = 0; i < list.length; i++) {      for (let j = i + 1; j < list.length; j++) {        if (list[i][0] <= list[j][1] && list[j][0] <= list[i][1]) {          list[i] = [Math.min(list[i][0], list[j][0]), Math.max(list[i][1], list[j][1])];          list.splice(j, 1);          changed = true;          break outer;        }      }    }  }  return list.sort((a, b) => a[0] - b[0]);}console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]])); // [[1, 6], [8, 10], [15, 18]]console.log(merge([[1, 4], [4, 5]]));                    // [[1, 5]]
How it works

It is correct but slow. Every merge restarts the search, so the worst case is O(n³).

Approach 2Sort by start, then scan
The idea

Sort by start. Push the first interval. Then look at each next interval. If it starts at or before the end of the last interval, make that end longer. Otherwise, push it as a new interval.

JavaScript
function merge(intervals) {  const sorted = intervals.map((x) => [...x]).sort((a, b) => a[0] - b[0]);  const merged = [sorted[0]];  for (let i = 1; i < sorted.length; i++) {    const last = merged[merged.length - 1];    if (sorted[i][0] <= last[1]) last[1] = Math.max(last[1], sorted[i][1]);    else merged.push(sorted[i]);  }  return merged;}console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]])); // [[1, 6], [8, 10], [15, 18]]console.log(merge([[1, 4], [4, 5]]));                    // [[1, 5]]console.log(merge([[1, 10], [2, 3], [4, 5]]));           // [[1, 10]]
How it works

After sorting, only the last merged interval can overlap the next one, so one pass is enough. Taking the larger of the two ends handles an interval that lies completely inside the last one. It takes O(n log n) time and O(n) space.

Which approach should you use?

Use the sort and scan. (LeetCode 56.)

Q2Insert intervalMedium

You get a list of intervals that are sorted by start and do not overlap. You also get a new interval. Insert it and merge where needed. The list must stay sorted, with no overlaps.

Example 1
Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]
Explanation: [2,5] overlaps [1,3], so they merge into [1,5].
Example 2
Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: [4,8] overlaps [3,5], [6,7] and [8,10].
Stuck? Open one hint at a time
Hint 1
The list is already sorted and has no overlaps. Which intervals are surely not changed?
Hint 2
Split the list into three parts: before, overlapping, and after.
Show all 2 solutions with explanations
Approach 1Add it, sort, and merge
The idea

Push the new interval into the list. Then run the merge-intervals solution.

JavaScript
function insert(intervals, newInterval) {  const all = [...intervals, newInterval].sort((a, b) => a[0] - b[0]);  const merged = [[...all[0]]];  for (let i = 1; i < all.length; i++) {    const last = merged[merged.length - 1];    if (all[i][0] <= last[1]) last[1] = Math.max(last[1], all[i][1]);    else merged.push([...all[i]]);  }  return merged;}console.log(insert([[1, 3], [6, 9]], [2, 5])); // [[1, 5], [6, 9]]console.log(insert([], [5, 7]));               // [[5, 7]]
How it works

It is simple and correct. It takes O(n log n) because of the sort. The sort is not needed, because the input is already in order.

Approach 2Three phases in one pass
The idea

Copy the intervals that end before the new one starts. Take in the ones that start at or before its end. Copy the rest.

JavaScript
function insert(intervals, newInterval) {  const result = [];  let i = 0;  const n = intervals.length;  while (i < n && intervals[i][1] < newInterval[0]) result.push(intervals[i++]);  let [start, end] = newInterval;  while (i < n && intervals[i][0] <= end) {    start = Math.min(start, intervals[i][0]);    end = Math.max(end, intervals[i][1]);    i++;  }  result.push([start, end]);  while (i < n) result.push(intervals[i++]);  return result;}console.log(insert([[1, 3], [6, 9]], [2, 5]));                           // [[1, 5], [6, 9]]console.log(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])); // [[1, 2], [3, 10], [12, 16]]console.log(insert([[1, 5]], [2, 3]));                                   // [[1, 5]]
How it works

Each interval is visited once. It takes O(n) time and O(n) space for the output. The point of the question is to use the order that is already there.

Which approach should you use?

Use the three-phase pass, which is O(n). If you want a safe backup, mention the sort-and-merge version first. (LeetCode 57.)

Q3Non-overlapping intervalsMedium

You get some intervals. Return the fewest you must remove so that the rest do not overlap. Intervals that only touch at an end point do not overlap.

Example 1
Input: [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Explanation: Remove [1,3]. The rest do not overlap (touching is allowed).
Example 2
Input: [[1, 2], [1, 2], [1, 2]]
Output: 2
Explanation: Keep one of the three equal intervals.
Stuck? Open one hint at a time
Hint 1
Removing the fewest is the same as keeping the most. Where have you seen "the most intervals with no overlap" before?
Hint 2
Which interval should you keep first? The one that starts first, the shortest one, or the one that ends first?
Show all 3 solutions with explanations
Approach 1Dynamic programming: longest chain
The idea

Sort by start. dp[i] is the most intervals you can keep among the first i + 1, if interval i is the last one you keep. The answer is the total minus the best chain.

JavaScript
function eraseOverlapIntervals(intervals) {  const a = [...intervals].sort((x, y) => x[0] - y[0]);  const dp = new Array(a.length).fill(1);  let best = 0;  for (let i = 0; i < a.length; i++) {    for (let j = 0; j < i; j++) {      if (a[j][1] <= a[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);    }    best = Math.max(best, dp[i]);  }  return a.length - best;}console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])); // 1console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]));         // 2
How it works

It is correct, but it takes O(n²) time.

Approach 2Greedy: sort by end
The idea

Sort by end. Keep an interval whenever it starts at or after the end of the last one you kept. Remove every other interval.

JavaScript
function eraseOverlapIntervals(intervals) {  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);  let kept = 0, lastEnd = -Infinity;  for (const [start, end] of sorted) {    if (start >= lastEnd) { kept++; lastEnd = end; }  }  return intervals.length - kept;}console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])); // 1console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]));         // 2console.log(eraseOverlapIntervals([[1, 2], [2, 3]]));                 // 0
How it works

The interval that ends first leaves the most room (the exchange argument from lesson 47). It takes O(n log n) time.

Approach 3Sort by start, and on a clash drop the one that ends later
The idea

Sort by start. When the next interval overlaps the one you are holding, remove one of them. Keep the one that ends earlier.

JavaScript
function eraseOverlapIntervals(intervals) {  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);  let removed = 0;  let end = sorted[0][1];  for (let i = 1; i < sorted.length; i++) {    if (sorted[i][0] < end) {      removed++;      end = Math.min(end, sorted[i][1]);   // keep the one that ends earlier    } else {      end = sorted[i][1];    }  }  return removed;}console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])); // 1console.log(eraseOverlapIntervals([[1, 100], [2, 3], [4, 5]]));       // 1
How it works

It is also O(n log n) and also correct, because at each clash it keeps the better interval. The sort-by-end version is easier to prove.

Which approach should you use?

Sort by end. (LeetCode 435.)

Q4Minimum number of arrows to burst balloonsMedium

Balloons are given as [xStart, xEnd] on a line. An arrow shot straight up at x bursts every balloon with xStart <= x <= xEnd. Return the fewest arrows needed to burst all the balloons.

Example 1
Input: [[10, 16], [2, 8], [1, 6], [7, 12]]
Output: 2
Explanation: Shoot at x = 6 (this bursts [2,8] and [1,6]). Shoot again at x = 12 (this bursts [10,16] and [7,12]).
Example 2
Input: [[1, 2], [3, 4], [5, 6], [7, 8]]
Output: 4
Explanation: No two balloons share a point.
Stuck? Open one hint at a time
Hint 1
A group of balloons can share one arrow when they all overlap at one common point.
Hint 2
Sort by end, and shoot at the end of the first balloon.
Show all 2 solutions with explanations
Approach 1Sort by start, and track the shared overlap
The idea

Sort by start. Keep the part that all balloons in the current group share (the latest start and the earliest end). If the next balloon starts after the earliest end of the group, close the group with one arrow and start a new group.

JavaScript
function findMinArrowShots(points) {  const sorted = [...points].sort((a, b) => a[0] - b[0]);  let arrows = 1;  let groupEnd = sorted[0][1];                 // the earliest end in the current group  for (let i = 1; i < sorted.length; i++) {    if (sorted[i][0] > groupEnd) { arrows++; groupEnd = sorted[i][1]; }    else groupEnd = Math.min(groupEnd, sorted[i][1]);  }  return arrows;}console.log(findMinArrowShots([[10, 16], [2, 8], [1, 6], [7, 12]])); // 2console.log(findMinArrowShots([[1, 2], [3, 4], [5, 6], [7, 8]]));    // 4
How it works

The group shrinks to the part where all its balloons overlap. A new balloon joins only if it reaches that part. It takes O(n log n) time.

Approach 2Sort by end, shoot at each end
The idea

Sort by end. Shoot at the end of the first balloon. Every balloon that starts at or before that point is also burst. At the first balloon that starts later, shoot again at its end.

JavaScript
function findMinArrowShots(points) {  const sorted = [...points].sort((a, b) => a[1] - b[1]);  let arrows = 0, arrowAt = -Infinity;  for (const [start, end] of sorted) {    if (start > arrowAt) { arrows++; arrowAt = end; }  }  return arrows;}console.log(findMinArrowShots([[10, 16], [2, 8], [1, 6], [7, 12]])); // 2console.log(findMinArrowShots([[1, 2], [2, 3], [3, 4], [4, 5]]));    // 2console.log(findMinArrowShots([[1, 1]]));                            // 1
How it works

Shooting at the earliest end is as far right as possible while still bursting that balloon. So it catches the most later balloons. It takes O(n log n) time. It is the same loop as "remove the fewest", except that balloons that only touch count as hit.

Which approach should you use?

Either one works. Sort by end is shorter. (LeetCode 452.)

Q5Meeting roomsEasy

You get meeting times [start, end]. Decide whether one person could attend all of them. A meeting that ends exactly when another one starts does not clash.

Example 1
Input: [[0, 30], [5, 10], [15, 20]]
Output: false
Explanation: The meeting [0,30] overlaps both of the others.
Example 2
Input: [[7, 10], [2, 4]]
Output: true
Explanation: After sorting, the order is [2,4] then [7,10]. They do not clash.
Stuck? Open one hint at a time
Hint 1
If the meetings were in order of start time, which pairs would you need to check?
Show all 2 solutions with explanations
Approach 1Check every pair
The idea

Compare every two meetings. Return false if any pair overlaps.

JavaScript
function canAttendMeetings(meetings) {  for (let i = 0; i < meetings.length; i++) {    for (let j = i + 1; j < meetings.length; j++) {      if (meetings[i][0] < meetings[j][1] && meetings[j][0] < meetings[i][1]) return false;    }  }  return true;}console.log(canAttendMeetings([[0, 30], [5, 10], [15, 20]])); // falseconsole.log(canAttendMeetings([[7, 10], [2, 4]]));            // true
How it works

It takes O(n²) time. Notice the strict <: a meeting that ends at 10 and another that starts at 10 do not clash.

Approach 2Sort by start and check neighbours
The idea

After sorting by start, a clash can only happen between neighbours. Return false if any meeting starts before the previous one ends.

JavaScript
function canAttendMeetings(meetings) {  const sorted = [...meetings].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;  }  return true;}console.log(canAttendMeetings([[0, 30], [5, 10], [15, 20]])); // falseconsole.log(canAttendMeetings([[7, 10], [2, 4]]));            // trueconsole.log(canAttendMeetings([[1, 5], [5, 9]]));             // trueconsole.log(canAttendMeetings([]));                           // true
How it works

Say meeting k clashes with some earlier meeting j, so k starts before j ends. Look at the meeting right after j. It starts no later than k, so it also starts before j ends. That means j clashes with its own neighbour. So if any clash exists, a clash between neighbours exists too. It takes O(n log n) time.

Which approach should you use?

Sort and check neighbours. This problem is only for paying members on LeetCode (252, "Meeting Rooms"), so the full problem is written out here.

Q6Meeting rooms IIMedium

You get meeting times [start, end]. Return the fewest meeting rooms you need. A meeting that ends at time t and one that starts at time t can share a room.

Example 1
Input: [[0, 30], [5, 10], [15, 20]]
Output: 2
Explanation: The meeting [0,30] runs the whole time. The other two never run together.
Example 2
Input: [[7, 10], [2, 4]]
Output: 1
Explanation: They never overlap.
Stuck? Open one hint at a time
Hint 1
The number of rooms you need equals the largest number of meetings happening at the same moment.
Hint 2
That largest number always happens at the start time of some meeting.
Hint 3
You only need the starts in order and the ends in order. You do not need to know which end belongs to which start.
Show all 3 solutions with explanations
Approach 1Count overlaps at each start
The idea

For the start time of every meeting, count how many meetings are running at that moment. The answer is the largest count.

JavaScript
function minMeetingRooms(meetings) {  let best = 0;  for (const [t] of meetings) {    let running = 0;    for (const [s, e] of meetings) if (s <= t && t < e) running++;    best = Math.max(best, running);  }  return best;}console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]])); // 2console.log(minMeetingRooms([[7, 10], [2, 4]]));            // 1
How it works

O(n²).

Approach 2Event sweep: +1 at starts, −1 at ends
The idea

A sweep walks along the time line once, from left to right, and handles the events in order. Make a list of events: a time, with +1 for a start and −1 for an end. Sort by time. If times are equal, put ends before starts. Keep a running total. The answer is the highest value it reaches.

JavaScript
function minMeetingRooms(meetings) {  const events = [];  for (const [s, e] of meetings) { events.push([s, 1]); events.push([e, -1]); }  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);   // at the same time, -1 (an end) comes first  let running = 0, best = 0;  for (const [, delta] of events) {    running += delta;    best = Math.max(best, running);  }  return best;}console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]])); // 2console.log(minMeetingRooms([[7, 10], [2, 4]]));            // 1console.log(minMeetingRooms([[1, 5], [5, 9], [9, 12]]));    // 1
How it works

It takes O(n log n) time. The rule for equal times matters: a meeting that ends at 5 frees its room for one that starts at 5.

Approach 3Two sorted lists, two pointers
The idea

Sort the starts and the ends separately. Go through the starts in order. If a start is before the earliest end that is still waiting, you need a new room. Otherwise, reuse that room and move the end pointer forward.

JavaScript
function minMeetingRooms(meetings) {  const starts = meetings.map((m) => m[0]).sort((a, b) => a - b);  const ends = meetings.map((m) => m[1]).sort((a, b) => a - b);  let rooms = 0, e = 0;  for (let s = 0; s < starts.length; s++) {    if (starts[s] < ends[e]) rooms++;    else e++;  }  return rooms;}console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]])); // 2console.log(minMeetingRooms([[7, 10], [2, 4]]));            // 1console.log(minMeetingRooms([[1, 5], [5, 9], [9, 12]]));    // 1
How it works

It takes O(n log n) time and needs no heap. It does not matter that the ends are sorted separately. We only ask whether some meeting has already ended, never which one. (The usual other way, a min-heap of end times, gives the same answer.)

Which approach should you use?

Use the two-pointer version or the event sweep. Both are easy to write without a heap. This problem is only for paying members on LeetCode (253, "Meeting Rooms II"), so the full problem is written out here.

Q7Interval list intersectionsMedium

You get two lists of closed intervals (both ends included). Each list is sorted, and no two intervals in the same list overlap. Return the places where they overlap, also as a sorted list of intervals.

Example 1
Input: A = [[0, 2], [5, 10], [13, 23], [24, 25]], B = [[1, 5], [8, 12], [15, 24], [25, 26]]
Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]
Explanation: For example, [5,10] meets [1,5] at the single point 5, and it meets [8,12] in [8,10].
Example 2
Input: A = [[1, 3], [5, 9]], B = []
Output: []
Explanation: B is empty, so nothing intersects.
Stuck? Open one hint at a time
Hint 1
The part that two intervals share goes from the later start to the earlier end, if that range makes sense.
Hint 2
Both lists are sorted. After you handle a pair, which interval can you drop?
Show all 2 solutions with explanations
Approach 1Compare every pair
The idea

For every interval in A and every interval in B, work out the overlap. Keep it if it is valid.

JavaScript
function intervalIntersection(A, B) {  const result = [];  for (const a of A) {    for (const b of B) {      const lo = Math.max(a[0], b[0]);      const hi = Math.min(a[1], b[1]);      if (lo <= hi) result.push([lo, hi]);    }  }  return result.sort((x, y) => x[0] - y[0]);}console.log(intervalIntersection([[1, 3], [5, 9]], [[2, 6]])); // [[2, 3], [5, 6]]
How it works

It takes O(m · n) time. It ignores that both lists are sorted.

Approach 2Two pointers
The idea

Look at A[i] and B[j]. Save their overlap, if there is one. Then move past whichever ends first, because it cannot overlap anything later in the other list.

JavaScript
function intervalIntersection(A, B) {  const result = [];  let i = 0, j = 0;  while (i < A.length && j < B.length) {    const lo = Math.max(A[i][0], B[j][0]);    const hi = Math.min(A[i][1], B[j][1]);    if (lo <= hi) result.push([lo, hi]);    if (A[i][1] < B[j][1]) i++; else j++;  }  return result;}console.log(intervalIntersection([[1, 3], [5, 9]], [[2, 6]]));  // [[2, 3], [5, 6]]console.log(intervalIntersection([[1, 3], [5, 9]], []));        // []console.log(intervalIntersection([[1, 7]], [[3, 10]]));         // [[3, 7]]
How it works

Each step moves a pointer forward, so there are at most m + n steps. That is O(m + n) time. The output is already sorted.

Which approach should you use?

Use two pointers. It is very similar to merging two sorted lists. (LeetCode 986.)

Make it stick

Make it stick — close this page, then
  1. Write the overlap test for two intervals, and explain when you use < and when you use <=.
  2. Explain why merge sorts by start, but "remove the fewest" sorts by end.
  3. Describe the three phases of insert interval.
  4. Explain why meeting rooms II works with starts and ends sorted separately.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

That finishes this part on heaps, greedy choices and intervals. Lesson 49 starts the next part with graphs. A graph is a set of nodes joined by edges (think of cities joined by roads). You will learn how to store graphs and how to search them.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Related series