Merge overlapping time intervals efficiently
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of closed intervals [start, end] with 0 <= start <= end, merge all intervals that overlap or touch and return a minimal set of non-overlapping intervals sorted by start. Implement an algorithm with O(n log n) time (due to sorting) and as little extra space as possible beyond the output. Clarify how to treat touching endpoints (e.g., [1,3] and [3,5]), zero-length intervals (e.g., [4,4]), and invalid inputs. Provide tests for nested intervals, duplicates, already-sorted input, reverse-sorted input, and large inputs (up to 1e5 intervals).
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.
Given a collection of closed intervals [start, end], merge every pair of intervals that overlap or touch, and return the minimal set of non-overlapping intervals sorted by start time.
Because the intervals are closed, touching endpoints count as connected. For example, [1,3] and [3,5] must be merged into [1,5]. Zero-length intervals such as [4,4] are valid and should be handled normally.
If the input is empty, return an empty list. If any interval is malformed, contains non-integer values, has negative values, or has start > end, raise a ValueError.
Your algorithm should run in O(n log n) time, which is optimal here because sorting is required in the general case. To minimize extra space, you may reorder the input intervals in place.
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.
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.