[LeetCode] 56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

合并区间。

题意是给一个二维数组，其中每个元素给的是一个类似[start, end]的范围。要求把这些区间尽可能地merge在一起。这题又是用到扫描线的思想。首先需要根据start对input排序，然后从第二个interval SECOND开始，跟其之前的interval FIRST作比较。比较的方式是

如果SECOND[start] > FIRST[end] - 说明两个interval没有交集，直接把FIRST加入最后的结果集
如果SECOND[start] <= FIRST[end] - 说明两个interval有交集，需要merge。merge后的interval的start自然是FIRST[start]，但是merge后的end是比较FIRST[end]和SECOND[end]谁大

时间O(nlogn) - 因为有sort

空间O(n) - 存放了最后的输出

JavaScript实现

 1 /**
 2  * @param {number[][]} intervals
 3  * @return {number[][]}
 4  */
 5 var merge = function (intervals) {
 6     // corner case
 7     if (intervals === null || intervals.length === 0) {
 8         return intervals;
 9     }
10 
11     // normal case
12     let res = [];
13     intervals.sort((a, b) => a[0] - b[0]);
14     let cur = intervals[0];
15     res.push(cur);
16     for (let interval of intervals) {
17         if (interval[0] <= cur[1]) {
18             cur[1] = Math.max(cur[1], interval[1]);
19         } else {
20             cur = interval;
21             res.push(cur);
22         }
23     }
24     return res;
25 };

Java实现

 1 class Solution {
 2     public int[][] merge(int[][] intervals) {
 3         // corner case
 4         if (intervals.length <= 1) {
 5             return intervals;
 6         }
 7 
 8         // normal case
 9         Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
10         List<int[]> res = new ArrayList<>();
11         int[] cur = intervals[0];
12         res.add(cur);
13         for (int[] interval : intervals) {
14             if (interval[0] <= cur[1]) {
15                 cur[1] = Math.max(cur[1], interval[1]);
16             } else {
17                 cur = interval;
18                 res.add(cur);
19             }
20         }
21         return res.toArray(new int[res.size()][]);
22     }
23 }

扫描线相关题目

LeetCode 题目总结