企业官网建设流程全解析

题目：

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input:intervals = [[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:intervals = [[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.

Constraints:

• intervals[i][0] <= intervals[i][1]

题目要求是给了一个数组of数组表示一系列时间段，要求把所有overlap的时间段结合起来。刚开始也是没啥思路，直接看答案了。答案的做法非常巧妙，首先把整个数组按开始时间排序，并维护一个list来存放merge后的结果。我们遍历排好序的数组，并将当前遍历的那个时间段和merge好的最晚时间段进行比较。如果merge好的最晚时间的结束时间比当前遍历的开始时间要早，或者当前是第一个遍历的，那就直接将当前遍历的时间段加入结果集，不需要进行任何其他操作。而如果当前遍历的时间段开始的比结果集中最晚的结束时间要早，就需要取结果集中最晚时间的结束时间，和当前遍历的这个时间段的结束时间之中的最大值！注意这里不能简单地取当前的结束时间，因为可能会有这样的例子[1, 4], [2, 3]。最后把linkedlist转换成array，需要注意的是如果直接采用toArray()，需要在参数里面加上一个instance，不然会出现编译错误incompatible type。时间复杂度O(nlogn)。

Runtime: 6 ms, faster than 62.09% of Java online submissions for Merge Intervals.

Memory Usage: 41.5 MB, less than 98.53% of Java online submissions for Merge Intervals.

class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[0] - b[0]); LinkedList<int[]> resultList = new LinkedList<>(); for (int[] interval : intervals) { if (resultList.size() == 0 || interval[0] > resultList.getLast()[1]) { resultList.add(interval); } else { int[] lastInterval = resultList.getLast(); lastInterval[1] = Math.max(interval[1], lastInterval[1]); } } return resultList.toArray(new int[resultList.size()][]); } }

2026.10.22

思路大概记得差不多但是完全忘了要取Math.max(lastInterval[1], interval[1])了，于是在以前写的里特意加粗了一下……以及确实写的不是那么优雅。以前用的居然是LinkedList作为List，没想到啊。

class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> result = new ArrayList<>(); for (int[] interval : intervals) { // the first interval if (result.isEmpty()) { result.add(interval); continue; } int[] lastInterval = result.get(result.size() - 1); if (interval[0] <= lastInterval[1]) { lastInterval[1] = Math.max(interval[1], lastInterval[1]); } else { result.add(interval); } } return result.toArray(new int[result.size()][]); } }