区间重叠

本人没有算法基础，以下均为春招刷Leetcode的笔记，仅用于记录，侵权勿喷

今天刷题时发现一类区间重叠题，思路很巧妙，理解后做起来非常简单

这类题的特点就是给你一组区间，求最多多少个区间重叠

会议室Ⅱ

leetcode

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间，返回所需会议室的最小数量
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

思路

我们将区间转化为两次操作，对于每一个区间，区间开始会申请一个会议室，区间结束会释放一个会议室

将操作按发生时间排序，依次执行，记录占用会议室的最大数量

实现

int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<vector<int>> v;
        for(auto& i : intervals){
            v.push_back({i[0], 1});		// 区间开始申请一个会议室
            v.push_back({i[1], -1});	// 区间结束释放一个会议室
        }
        sort(v.begin(), v.end());	// 将操作按发生时刻排序，对于同时发生的操作，先释放再申请
        /*
        sort(v.begin(), v.end(), [](const vector<int>& a, const vector<int>& b)->bool{
            if(a[0] == b[0]){
                return a[1] < b[1];
            }
            return a[0] < b[0];
        });
        */
        int ans = 0;
        int cur = 0;
        for(int i = 0; i < v.size(); ++i){
            cur += v[i][1];
            ans = max(ans, cur);
        }
        return ans;
    }

拼车

leetcode

车上最初有 capacity 个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）

数组每一项包含三个数，上车人数，上车时刻，下车时刻

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

思路

与上题基本相同，不过每次操作的数量改变了

实现

bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<vector<int>> v;
        for(auto& t: trips){
            v.push_back({t[1], t[0]});
            v.push_back({t[2], -t[0]});
        }
        sort(v.begin(), v.end());
        int cur = 0;
        for(int i = 0; i < v.size(); ++i){
            cur += v[i][1];
            if(cur > capacity){
                return false;
            }
        }
        return true;
    }

算法：区间重叠

区间重叠

会议室Ⅱ

思路

实现

拼车

思路

实现