Vibed to Cracked
Sign In
Meta Questions

Given a list of intervals, merge all overlapping intervals.

MediumTechnicalAlgorithms10-15 minutes

Model Answer

Sort intervals by start time, then iterate and merge overlapping ones. Two intervals overlap if the current interval's start is less than or equal to the previous interval's end.

Approaches

Sort and Merge

Sort by start time, then linearly scan and merge overlapping intervals by comparing current start with the last merged interval's end.

function merge(intervals) {
  if (intervals.length <= 1) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      merged.push(intervals[i]);
    }
  }
  return merged;
}
Time: O(n log n) due to sortingSpace: O(n) for the output

Common Mistakes

  • 1.Forgetting to sort the intervals first
  • 2.Using start of current vs. end of current instead of end of previous for overlap check
  • 3.Not updating the end to be the max of both ends when merging
  • 4.Modifying the input array in place without being asked

Follow-up Questions

  • What if a new interval is being inserted into an already-merged list?
  • How would you find the minimum number of meeting rooms needed?
  • What if intervals have weights and you need to find the maximum overlapping weight?
Given a list of intervals, merge all overlapping intervals. | Meta Interview