Katkat
Back

Merge overlapping time intervals

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate array-based data using sorting and linear scanning to identify and merge overlapping intervals.

Merge Overlapping Intervals

Given a collection of intervals represented as a list of [start, end] pairs, write a function to merge all overlapping intervals and return a new list of the non-overlapping intervals that cover all the intervals in the input.

Function Signature

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

Constraints

  • 0 <= len(intervals) <= 10^4
  • 0 <= start < end <= 10^6

Examples

Example 1: Input: [[1, 3], [2, 6], [8, 10], [15, 18]] Output: [[1, 6], [8, 10], [15, 18]] Explanation: Since [1, 3] and [2, 6] overlap, they are merged into [1, 6].

Example 2: Input: [[1, 4], [4, 5]] Output: [[1, 5]] Explanation: Intervals that share a boundary point are considered overlapping.

Edge Cases

  • Empty input list.
  • A list containing a single interval.
  • Intervals fully contained within another interval (e.g., [1, 10] and [2, 5]).
  • Intervals already sorted or completely unsorted.

Hints

Hint 1

Consider sorting the intervals by their start times to simplify the merging process.

Hint 2

Once sorted, you can iterate through the list and track the 'current' interval being compared against the next one in the sorted sequence.

Hint 3

If the start time of the next interval is less than or equal to the end time of the current interval, they overlap; otherwise, the current interval is complete.

Follow-up questions

  • What is the time and space complexity of your approach, and can you optimize the space complexity further?
  • How would your algorithm change if you needed to insert a new interval into an already merged list of intervals?
  • If the intervals were already sorted by start time, how would that affect your time complexity?