算法leetcode｜56. 合并区间（rust重拳出击）

56. 合并区间：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

样例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

样例 2：

输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

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

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 如果没想到排序是比较麻烦的，而下定决定使用排序也不是那么容易，因为排序本身的时间复杂度也不低，但是对于这个情况来说，还是很值得的。
• 区间有两个值，应该按照开始值排序，而不是末尾值，当然逆向处理也是可以的，但是违背常理。
• 根据区间开始值排序，前一个区间的末尾和下一个区间的开始值会出现几种情况：
  1. 前一个区间和后一个区间没有交集，那么当前区间就处理完毕，直接开始处理下一个区间。
  2. 前一个区间和后一个区间有部分重叠，那么就将两个区间合并，然后接着处理下一个区间。
  3. 前一个区间完整包含了后一个区间，那么直接抛弃后一个区间，然后继续处理下一个区间。
• 后两种情况可以统一认为是有重叠，只需要统一处理为更新当前处理区间的末尾值即可。

题解：

rust：

impl Solution {pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {intervals.sort_unstable();let mut ans: Vec<Vec<i32>> = Vec::new();let (mut l, mut r) = (intervals[0][0], intervals[0][1]);intervals.iter().skip(1).for_each(|cur| {if r < cur[0] {// 没重合ans.push(vec![l, r]);l = cur[0];r = cur[1];} else {// 重合r = r.max(cur[1]);}});ans.push(vec![l, r]);return ans;}
}

go：

func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})var ans [][]intlast := intervals[0]for i := 1; i < len(intervals); i++ {cur := intervals[i]if last[1] < cur[0] {// 没有重合ans = append(ans, last)last = cur} else {// 有重合if cur[1] > last[1] {last[1] = cur[1]}}}ans = append(ans, last)return ans
}

c++：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());vector<vector<int>> ans;for (int i = 0; i < intervals.size(); ++i) {const int l = intervals[i][0], r = intervals[i][1];if (ans.empty() || ans.back()[1] < l) {ans.push_back({l, r});} else {ans.back()[1] = max(ans.back()[1], r);}}return ans;}
};

python：

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x: x[0])ans = []for interval in intervals:if not ans or ans[-1][1] < interval[0]:# 不重合ans.append(interval)else:# 重合ans[-1][1] = max(ans[-1][1], interval[1])return ans

java：

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));final List<int[]> ans  = new ArrayList<int[]>();int[]             last = intervals[0];for (int i = 1; i < intervals.length; ++i) {final int[] cur = intervals[i];if (last[1] < cur[0]) {// 没重合ans.add(last);last = cur;} else {// 重合last[1] = Math.max(last[1], cur[1]);}}ans.add(last);return ans.toArray(new int[ans.size()][]);}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~