Coding

Merge Overlapping Subintervals

Asked at

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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

You can return the intervals in any order.

**Input: **intervals = [[1,5],[3,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Intervals [1,5] and [3,6] overlap, so they are merged into [1,6].

**Input: **intervals = [[5,7],[1,3],[4,6],[8,10]] Output: [[1,3],[4,7],[8,10]] Explanation: Intervals [4,6] and [5,7] overlap and are merged into [4,7].

**Input: **intervals = [[1,4],[4,5]]

1 <= intervals.length <= 10⁵
0 <= starti <= endi <= 10⁵

cpp

class Solution {
  public:
    vector<vector<int>> mergeOverlap(vector<vector<int>>& arr) {
        // Your code goes here
    }
};

java

class Solution {
    public List<List<Integer>> mergeOverlap(List<List<Integer>> intervals) {
        // Your code goes here
    }
}

python

class Solution:
    def mergeOverlap(self, intervals):
        # Your code goes here

javascript

class Solution {
    mergeOverlap(intervals) {
        // Your code goes here
    }
}

csharp

class Solution
{
    public List<List<int>> MergeOverlap(List<List<int>> intervals)
    {
        // Your code goes here
    }
}

func mergeOverlap(arr [][]int) [][]int {
  // Your code goes here
}

Stuck? Show a way to structure it+

01Sort by start time.
02Initialize the current merged interval.
03Merge when the next start is within the current end.
04Otherwise emit current and start a new one.
05Emit the final interval.

Reference answer

Sort intervals by start, with end as a tie-breaker if useful. Maintain one current merged interval. If the next interval starts at or before current.end, the two overlap or touch, so extend current.end = max(current.end, next.end). Otherwise there is a gap: append current to the result and start a new current interval. Append the final current interval after the loop. The sorted order means no earlier interval can later bridge a gap, which is why this greedy scan is correct. Decide whether touching endpoints should merge based on the problem's closed-interval convention; the standard version uses next.start <= current.end. Sorting is O(N log N), scanning O(N), and output space is O(N).

Then expect these follow-ups

How would you insert one additional interval?
Tests: interval reasoning
How would you compute total covered length?
Tests: aggregation

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question