FastPrep
Problem · Intervals

Merge Intervals

Learn this problem
● EasyAmazon logoAmazonINTERNNEW GRADOAONSITE INTERVIEW
See Amazon hiring insights

Problem statement

Given an array of closed intervals where intervals[i] = [start_i, end_i], merge every pair of overlapping intervals.

Return the non-overlapping intervals that cover every interval in the input, sorted by start time. Intervals that share an endpoint are considered overlapping.

Function

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

Examples

Example 1

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

Intervals [1,3] and [2,6] overlap, so they merge into [1,6].

Example 2

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

The intervals share endpoint 4, so they merge into [1,5].

Example 3

intervals = [[8,10],[1,4],[2,3],[15,18],[6,9],[3,7],[17,20],[12,12]]return = [[1,10],[12,12],[15,20]]

The intervals are intentionally unsorted. After sorting by start time, [1,4], [2,3], [3,7], [6,9], and [8,10] form one connected overlap chain and merge into [1,10]. Interval [12,12] remains separate, while [15,18] and [17,20] merge into [15,20].

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^4

More Amazon problems

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