Merge Intervals
Given an array of intervals, merge all overlapping intervals and return the array of non-overlapping intervals.
Why Interviewers Ask This
Google asks 'Merge Intervals' to evaluate a candidate's ability to handle sorting logic and edge cases in real-world scheduling or resource allocation problems. Interviewers specifically look for how you approach data normalization, your grasp of time complexity trade-offs, and whether you can systematically reduce overlapping states without missing boundary conditions.
How to Answer This Question
1. Clarify Requirements: Confirm if intervals are inclusive, if the input is sorted, and how to handle touching intervals like [1,2] and [2,3].
2. Optimize Strategy: Propose sorting the intervals by start time first. This transforms the problem into a linear scan rather than a brute-force O(n^2) comparison.
3. Initialize State: Create a result list and push the first interval as the current active range.
4. Iterate and Merge: Loop through remaining intervals. If the current interval starts before or exactly when the active one ends, extend the active end to the maximum of both ends.
5. Finalize: If no overlap exists, push the active interval to results and reset it to the new interval. Always mention O(n log n) time complexity due to sorting and O(n) space for output.
Key Points to Cover
- Explicitly stating the decision to sort by start time first
- Demonstrating clear handling of the 'touching' interval edge case
- Using a single pass linear scan after sorting for optimal performance
- Correctly identifying the max function for merging end points
- Articulating the O(n log n) time complexity clearly
Sample Answer
To solve this efficiently, I would first sort the intervals based on their starting times. This is crucial because it allows us to process overlaps sequentially without needing nested loops. For example, given [[1,3],[2,6],[8,10],[15,18]], sorting ensures we encounter [1,3] before [2,6].
I'd initialize a result list and add the first interval as my current merged interval. Then, I iterate through the rest. When comparing the current interval with the last added one, I check if the current start is less than or equal to the previous end. In our example, 2 is less than 3, so they overlap. I merge them by updating the previous end to Math.max(3, 6), resulting in [1,6].
Next, I compare [8,10] with [1,6]. Since 8 is greater than 6, there is no overlap, so I push [1,6] to the final list and start tracking [8,10] as the new current interval. This pattern continues until all intervals are processed. Finally, I ensure the last active interval is added to the list. This approach runs in O(n log n) time due to sorting, which Google values for scalability, and handles edge cases like single intervals or fully contained ranges naturally.
Common Mistakes to Avoid
- Failing to sort the input array, leading to an inefficient O(n^2) brute force solution
- Incorrectly handling edge cases where intervals just touch, such as [1,2] and [2,3]
- Forgetting to add the final active interval to the result list after the loop finishes
- Not considering empty input arrays or arrays with only one interval
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.