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

Python爱好者社区 · 公众号 · Python · 2025-02-21 11:59

正文

付费上班曾经是一句玩笑，没想到现在却变成了现实。最近一网友开了一家假装上班公司，每天只需要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<int[]> 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<vector<int>> merge(vector<vector<int>> &intervals) {
        // 按照起始点对数组进行排序
        sort(intervals.begin(), intervals.end());
        int start = intervals[0][0];
        int

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

正文

请到「今天看啥」查看全文