力扣3169. 无需开会的工作日

 

给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。

返回员工可工作且没有安排会议的天数。

注意：会议时间可能会有重叠。

示例 1：

输入：days = 10, meetings = [[5,7],[1,3],[9,10]]

输出：2

解释：

第 4 天和第 8 天没有安排会议。

示例 2：

输入：days = 5, meetings = [[2,4],[1,3]]

输出：1

解释：

第 5 天没有安排会议。

示例 3：

输入：days = 6, meetings = [[1,6]]

输出：0

解释：

所有工作日都安排了会议。

提示：

• 1 <= days <= 109
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

代码思路：本来思路是先sort排序，排好序以后假如遍历结果存在，就标记flag为1，最后便利数组，如果flag为0则代表没有安排会议，输出计数 。

代码是

class Solution {
public:int countDays(int days, vector<vector<int>>& meetings) {// 创建标记数组vector<int> flag(days, 0);// 遍历会议并标记会议天数for (const auto& meeting : meetings) {int start = meeting[0];int end = meeting[1];for (int i = start - 1; i <= end - 1; ++i) {flag[i] = 1;}}// 统计没有安排会议的天数int cnt = 0;for (int i = 0; i < days; ++i) {if (flag[i] == 0) {cnt++;}}return cnt;}
};

结果没有通过全部样例，超界了。只能用合并区间的思路。

思路：假如上一个会议还没有结束下一个会议就开始的话，cnt+= 他们之间的天数差距，也就是空闲的天数。如果最后剩下了，最后一个位子不等于meetings的最后一个位子，就再加上最后的几天空闲

class Solution {
public:int countDays(int days, vector<vector<int>>& meetings) {// 先将会议区间按开始天数排序sort(meetings.begin(), meetings.end());int cnt = 0;int lastEnd = 0;// 遍历所有会议区间for (const auto& meeting : meetings) {int start = meeting[0];int end = meeting[1];// 计算上一个会议结束到当前会议开始之间的空闲天数if (start > lastEnd + 1) {cnt += start - lastEnd - 1;}// 更新最后一个会议的结束时间lastEnd = max(lastEnd, end);}// 如果最后一个会议结束后还有空闲天数if (lastEnd < days) {cnt += days - lastEnd;}return cnt;}
};