FastPrep
Problem · Array

Merge Intervals

Learn this problem
● MediumMicro1 logoMicro1FULLTIMEOA

Problem statement

Given an array of closed integer intervals intervals, where intervals[i] = [start_i, end_i] and start_i <= end_i, merge every pair of intervals that overlaps.

Because the intervals are closed, two intervals overlap when the next start is less than or equal to the current merged end. Return the non-overlapping merged intervals ordered by increasing start value.

Function

merge(intervals: int[][]) → int[][]

Examples

Example 1

intervals = [[1,3],[2,6],[8,10],[15,18]]return = [[1,6],[8,10],[15,18]]

The intervals [1,3] and [2,6] overlap, so they merge into [1,6]. The remaining intervals do not overlap that merged interval or each other.

Example 2

intervals = [[1,4],[4,5]]return = [[1,5]]

The intervals meet at the closed endpoint 4, so they overlap and merge into [1,5].

Example 3

intervals = [[5,7],[1,2],[2,4]]return = [[1,4],[5,7]]

Sorting by start gives [1,2], [2,4], and [5,7]. The first two overlap at endpoint 2; the last interval remains separate.

Constraints

  • 1 <= intervals.length <= 100000.
  • Every interval contains exactly two integers.
  • -10^9 <= start_i <= end_i <= 10^9.
drafts saved locally
public int[][] merge(int[][] intervals) {
    // Write your code here.
}
intervals[[1,3],[2,6],[8,10],[15,18]]
expected[[1,6],[8,10],[15,18]]
checking account