这是一个创建于 2666 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2:
输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。 题解
这个题的基本思路就是当两个区间有重合的时候,第一个区间的 end >= 第二个区间的 start。前提是我们都是从小到大排好序的。那么合并完的区间就是[第一个区间的 start, 第二个区间的 end]。遍历结束,即可得到最终的解。
/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ class Solution { public List<Interval> merge(List<Interval> intervals) { // sort start&end int n = intervals.size(); int[] starts = new int[n]; int[] ends = new int[n]; for (int i = 0; i < n; i++) { starts[i] = intervals.get(i).start; ends[i] = intervals.get(i).end; } Arrays.sort(starts); Arrays.sort(ends); // loop through int i = 0; List<Interval> res = new ArrayList<>(); while (i < n) { int st = starts[i]; while (i < n - 1 && starts[i + 1] <= ends[i]) i++; int en = ends[i]; res.add(new Interval(st, en)); i++; } return res; } } 热门阅读
最近在刷题，有一起的可以加手撕代码群：805423079 
 | 1 ihainan 2018-08-29 20:32:59 +08:00 [第一个区间的 start, 第二个区间的 end] 这是错的，应该是 [第一个区间的 start, 区间最大的 end]，举例：[1, 4], [2, 3]。 |
 | 3 wind3110991 2018-08-30 10:36:25 +08:00 def merge(region_list): total_region = [] if not test_list: return [] for region in region_list: if not total_region: total_region = region_list[0] continue # min if total_region[0] > region[0]: total_region[0] = region[0] # max if total_region[1] < region[1]: total_region[1] = region[1] return total_region test_list = [[1,3],[2,6],[8,10],[15,18]] test_list2 = [[1,4],[4,5]] l1 = merge(test_list) l2 = merge(test_list2) print l1, l2 |
 | 4 Raisu 2018-08-30 11:10:45 +08:00 via Android 一天一道太小了吧。。。 |
| 6 Raisu 2018-09-12 23:58:39 +08:00 我现在基本一天 3-5 道题，不过都是做的 easy，等做到 100 道以后就准备复习一下算法再做 medium 100 道。不知道到时候面试能过不 |
 | 7 pg633 2018-12-10 10:07:45 +08:00 困难 随便切 ，中等 各种卡 |
Select Language