付费上班终于成为了现实。

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

付费上班曾经是一句玩笑，没想到现在却变成了现实。最近一网友开了一家假装上班公司，每天只需要30元，中午还提供一顿饭。

之前在网上也经常看到某某失业之后不敢让家里人知道，白天就到公园里闲逛，假装去上班，还有的是去星巴克，一坐就是一整天。其实我觉得这个真没必要，失业又不是得了绝症，和家里人沟通一下，还是能理解的，谁还没经历过失业？除了体制内的我估计至少80%的人都会经历过失业，有的还会经历过多次。失业没什么，没必要假装去上班。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第56题：合并区间。

问题描述

来源：LeetCode第56题

难度：中等

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

示例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^4

• intervals[i].length == 2

• 0 <= starti <= endi <= 10^4

问题分析

这题让合并区间，并且合并之后的区间没有重叠，实际上就是让把重叠的区间给合并，怎么判断区间有没有重叠呢？我们以示例一为例画个图来看下。

如上图所示，要判断两个区间有没有重叠，我们 先对所有区间按照起始点进行排序 ，排序之后如果 后面区间的起始点小于前面区间的终止点 ，比如区间[2,6]和区间[1,3]，那么这两个区间肯定有重叠，我们需要把他俩合并即可，合并之后的区间是[1,6]，然后这个区间还要继续和后面的区间比较。

如果 后面区间的起始点大于前面区间的终止点 ，比如上面合并之后的区间[1,6]和区间[8，10]，那么这两个区间肯定是没有重叠的，我们需要把前面的区间[1,6]添加到集合中，后面的区间[8，10]先不要添加，因为后面还需要查找和[8，10]有没有重叠的区间。

JAVA：

public int[][] merge(int[][] intervals) {     // 按照起始点对数组进行排序     Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));     int start = intervals[0][0];     int end = intervals[0][1];     List

  ans = new ArrayList<>();     for (int[] interval : intervals) {         if (interval[0] <= end) {// 当前区间和前面区间合并             end = Math.max(end, interval[1]);         } else {// 当前区间和前面区间不能合并，把前面的区间添加进来。             ans.add(new int[]{start, end});             start = interval[0];             end = interval[1];         }     }     ans.add(new int[]{start, end});// 最后的区间要单独添加。     // 把集合转为数组。     return ans.toArray(new int[ans.size()][]); }

C++：

public:     vector

 > merge(vector

 > &intervals) {         // 按照起始点对数组进行排序         sort(intervals.begin(), intervals.end());         int start = intervals[0][0];         int end = intervals[0][1];         vector

 > ans;         for (vector

  &interval: intervals) {             if (interval[0] <= end) {// 当前区间和前面区间合并                 end = max(end, interval[1]);             } else {// 当前区间和前面区间不能合并，把前面的区间添加进来。                 ans.push_back({start, end});                 start = interval[0];                 end = interval[1];             }         }         ans.push_back({start, end});// 最后的区间要单独添加。         return ans;     }

Python：

def merge(self, intervals: List[List[int]]) -> List[List[int]]:     # 按照起始点对数组进行排序     intervals.sort(key=lambda x: x[0])     ans = []     start, end = intervals[0][0], intervals[0][1]     for interval in intervals:         if interval[0] <= end:  # 当前区间和前面区间合并             end = max(end, interval[1])         else:  # 当前区间和前面区间不能合并，把前面的区间添加进来。             ans.append([start, end])             start = interval[0]             end = interval[1]     ans.append([start, end])  # 最后的区间要单独添加。     return ans

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。