Merge overlapping time intervals efficiently
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates a candidate's understanding of interval merging, sorting strategies, edge-case handling (including touching endpoints and zero-length intervals), and attention to time and space complexity when manipulating ranges.
Constraints
- 0 <= n <= 100000, where n is the number of intervals
- 0 <= start <= end <= 10^9 for every valid interval
- Each interval must contain exactly two integers; otherwise raise ValueError
Examples
Input: ([] ,)
Expected Output: []
Explanation: An empty input has no intervals to merge, so the result is an empty list.
Input: ([[1,10],[2,3],[4,8],[9,10]],)
Expected Output: [[1,10]]
Explanation: All intervals are contained within or touch the outer interval [1,10], so they collapse into one interval.
Input: ([[1,3],[1,3],[3,5],[4,4],[7,7],[7,7]],)
Expected Output: [[1,5],[7,7]]
Explanation: Duplicates merge naturally, [1,3] touches [3,5], and [4,4] lies inside the merged interval. The two [7,7] intervals merge into one.
Input: ([[0,1],[2,2],[2,4],[6,8]],)
Expected Output: [[0,1],[2,4],[6,8]]
Explanation: The input is already sorted. Only [2,2] and [2,4] touch and merge.
Input: ([[8,10],[6,7],[3,5],[1,3]],)
Expected Output: [[1,5],[6,7],[8,10]]
Explanation: After sorting, [1,3] touches [3,5] and becomes [1,5]. The other intervals stay separate.
Input: ([[30,31],[27,29],[29,30],[20,20],[18,19],[15,17],[17,18],[12,14],[10,11],[11,12],[5,5],[4,6],[2,3],[1,2],[40,45],[44,50]],)
Expected Output: [[1,3],[4,6],[10,14],[15,19],[20,20],[27,31],[40,50]]
Explanation: This larger mixed case creates several chains of touching or overlapping intervals. The same O(n log n) approach scales to inputs as large as 100000 intervals.
Solution
def solution(intervals):
if isinstance(intervals, tuple) and len(intervals) == 1 and isinstance(intervals[0], (list, tuple)):
intervals = intervals[0]
if not isinstance(intervals, (list, tuple)):
raise ValueError('intervals must be a list or tuple of [start, end] pairs')
if isinstance(intervals, tuple):
intervals = list(intervals)
if not intervals:
return []
for interval in intervals:
if not isinstance(interval, (list, tuple)) or len(interval) != 2:
raise ValueError('Each interval must contain exactly two integers')
start, end = interval
if type(start) is not int or type(end) is not int:
raise ValueError('Interval bounds must be integers')
if start < 0 or end < 0 or start > end:
raise ValueError('Each interval must satisfy 0 <= start <= end')
intervals.sort(key=lambda interval: interval[0])
merged = [[intervals[0][0], intervals[0][1]]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
if end > last_end:
merged[-1][1] = end
else:
merged.append([start, end])
return mergedTime complexity: O(n log n). Space complexity: O(k) for the output plus O(1) auxiliary in the merge step when sorting a list in place; Python's sort may use additional internal memory..
Hints
- Sort the intervals by their start value first. After that, you only need one left-to-right pass to merge them.
- Keep the last merged interval in the output and compare the next interval's start against its end. For closed intervals, start <= end means they should merge.