Leetcode大大，对不起你，我把你当成测试平台了

小码匠

发布于 2022-06-16 18:10:28

3360

文章被收录于专栏：小码匠和老码农小码匠和老码农

碎碎念

首先，我要为leetcode大大唱一首歌：听我说，谢谢你，因为有了你，温暖了四季，谢谢你，感谢有你，世界更美丽...
其次，我要向leetcode大大说一声：对不起，抱歉，我把你当测试平台用了

标签
贪心、动态规划

题目地址

435. 无重叠区间

https://leetcode.cn/problems/non-overlapping-intervals/

问题描述

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104

题解

当我看到这道题时，笑了，这不就是【カメのアルル】约会的变形题吗？对路

小码匠：第1次提交

测试case
- 通过：57
- 超时:1

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [&](vector<int> x, vector<int> y) {
        return x[1] < y[1];
    });
    int ans = intervals[0][1];
    int cnt = 1;
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i][0] < ans) {
            ans = min(ans, intervals[i][1]);
        } else {
            cnt++;
            ans = intervals[i][1];
        }
    }
    return intervals.size() - cnt;
}

小码匠：第2次提交

继续优化

删除了最小值判断处理，这个是没必要的逻辑

测试case

通过：57
超时:1

依然超时。。。

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [&](vector<int> x, vector<int> y) {
        return x[1] < y[1];
    });
    int ans = intervals[0][1];
    int cnt = 1;
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i][0] >= ans) {
            cnt++;
            ans = intervals[i][1];
        }
    }
    return intervals.size() - cnt;
}

小码匠：第3次提交

继续优化
- 怀疑是循环中每次计算size导致，把数字长度提取到了循环外面
测试case：真是打不死的小强，又over了
- 通过：57
- 超时:1

依然超时。。。

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [&](vector<int> x, vector<int> y) {
            return x[1] < y[1];
        });
        int ans = intervals[0][1];
        int cnt = 1;
        int len = intervals.size();
        for(int i = 1; i < len; i++) {
            if(intervals[i][0] >= ans) {
                cnt++;
                ans = intervals[i][1];
            }
        }
        return len - cnt;
    }

官方题解

实在没办法了，看题解，发现代码基本一致
提交官方题解：AC了

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return 0;
        }
        
        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
            return u[1] < v[1];
        });

        int n = intervals.size();
        int right = intervals[0][1];
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) {
                ++ans;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }

小码匠：第4次提交

继续优化：参照官方题解
- 修改了比较函数，用引用方式传递参数
- const定义参数
测试case：AC

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [&](const vector<int>& x, const vector<int>& y) {
            return x[1] < y[1];
        });
        int ans = intervals[0][1];
        int cnt = 1;
        int len = intervals.size();
        for(int i = 1; i < len; i++) {
            if(intervals[i][0] >= ans) {
                cnt++;
                ans = intervals[i][1];
            }
        }
        return len - cnt;
    }

复盘

OI赛场，容不得半点瑕疵

题目提交后，老码农又拉着我一起复盘

题目AC不是目的
知识点搞明白，学习大神们的思路
每天都要精进

老码农，你好啰嗦啊，天天跟我叨咕这些，耳朵都磨出茧子来了。

话说回来，复盘真的很有必要，从优化的角度

翻阅《C++程序设计语言第1～3部分》的【12章：函数】一节，大神给的建议
- 值传递是对象值拷贝，当对象特别大时，会比较耗时
- 引用传递，不需要分配独立的内存空间，实质是同一个对象
- 对于小对象使用值传递方式
- 对于你无需修改的大对象使用const引用传递
- 如果需要返回计算结果，最好使用return而非通过参数修改对象 -> 这条和本题没关系
翻阅侯捷大佬《Effective C++ 改善程序与设计的55个具体做法》
- 条款03: 尽可能使用const const的一件奇妙事情时，它准许你指定一个语义约束，而编译器会强制实施这项约束。它准许你告诉编译器和其他程序员某值应该保持不变。这要这是事实，你就该确实说出来，因为说出来可以获得编译器的囊助，确保这条约束不被违反
关于i++和++i区别，我习惯用i++，没有注意到++i的区别，老码农又拽给我一篇文章，让我自己去看，知道他也讲不明白