Katkat
Back

Merge overlapping intervals

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to manage and merge interval-based data, requiring sorting and a single-pass linear traversal to resolve overlaps.

Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Function Signature

def merge(intervals: List[List[int]]) -> List[List[int]]:

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

Examples

Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since [1,3] and [2,6] overlap, merge them into [1,6].

Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping and should be merged.

Edge Cases

  • An empty list of intervals.
  • A list containing a single interval.
  • Intervals that are entirely contained within others (e.g., [[1,10], [2,5]]).

Hints

Hint 1

Sort the intervals based on their start times to ensure that potential overlaps are adjacent in the list.

Hint 2

Initialize a list with the first interval and iterate through the sorted list, comparing the current interval's start with the last added interval's end.

Hint 3

If the current interval's start is less than or equal to the last added interval's end, merge them by updating the end of the last added interval to the maximum of both ends.

Follow-up questions

  • How would you modify your algorithm if the intervals were not sorted by start time?
  • What is the time and space complexity of your solution, and can you optimize the space if the input array is mutable?
  • If you were given a new interval to insert into an existing list of non-overlapping intervals, how would you perform that operation efficiently?