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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question