题目
给出一个区间的集合，请合并所有重叠的区间。
示例 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 
Select Language