Medium

题目描述

给你一个正整数 days，表示员工可以工作的总天数（从第 1 天开始）。同时给你一个大小为 n 的二维数组 meetings，其中 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 <= 10^9
  • 1 <= meetings.length <= 10^5
  • meetings[i].length == 2
  • 1 <= meetings[i][0] <= meetings[i][1] <= days

解题思路

这道题的核心思路是区间合并问题。我们需要找到所有没有被会议覆盖的天数。

解题步骤：

  1. 排序：首先按照会议开始时间对所有会议进行排序
  2. 合并重叠区间：遍历排序后的会议，将重叠的会议区间合并成一个大区间
  3. 计算空闲天数：统计合并后区间之间的空隙天数，以及开头和结尾的空闲天数

具体实现：

  • 排序后，依次检查相邻会议是否重叠（当前会议开始时间 ≤ 上一个会议结束时间）
  • 如果重叠，则合并区间（更新结束时间为两者最大值）
  • 如果不重叠，则计算空隙天数并开始新区间
  • 最后别忘记计算最后一个会议结束后到总天数结束的空闲天数

这种方法的时间复杂度主要由排序决定，为 O(n log n)，空间复杂度为 O(1)（不考虑排序额外空间）。

代码实现

class Solution {
public:
    int countDays(int days, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        
        int freeDays = 0;
        int lastEnd = 0;
        
        for (auto& meeting : meetings) {
            int start = meeting[0];
            int end = meeting[1];
            
            if (start > lastEnd + 1) {
                freeDays += start - lastEnd - 1;
            }
            
            lastEnd = max(lastEnd, end);
        }
        
        // 最后一个会议结束后的空闲天数
        if (lastEnd < days) {
            freeDays += days - lastEnd;
        }
        
        return freeDays;
    }
};

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        
        free_days = 0
        last_end = 0
        
        for start, end in meetings:
            if start > last_end + 1:
                free_days += start - last_end - 1
            
            last_end = max(last_end, end)
        
        # 最后一个会议结束后的空闲天数
        if last_end < days:
            free_days += days - last_end
        
        return free_days

public class Solution {
    public int CountDays(int days, int[][] meetings) {
        Array.Sort(meetings, (a, b) => a[0].CompareTo(b[0]));
        
        int freeDays = 0;
        int lastEnd = 0;
        
        foreach (var meeting in meetings) {
            int start = meeting[0];
            int end = meeting[1];
            
            if (start > lastEnd + 1) {
                freeDays += start - lastEnd - 1;
            }
            
            lastEnd = Math.Max(lastEnd, end);
        }
        
        // 最后一个会议结束后的空闲天数
        if (lastEnd < days) {
            freeDays += days - lastEnd;
        }
        
        return freeDays;
    }
}

var countDays = function(days, meetings) {
    meetings.sort((a, b) => a[0] - b[0]);
    
    let freeDays = 0;
    let lastEnd = 0;
    
    for (const [start, end] of meetings) {
        if (start > lastEnd + 1) {
            freeDays += start - lastEnd - 1;
        }
        
        lastEnd = Math.max(lastEnd, end);
    }
    
    // 最后一个会议结束后的空闲天数
    if (lastEnd < days) {
        freeDays += days - lastEnd;
    }
    
    return freeDays;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要开销在排序，其中 n 是会议数量
空间复杂度O(1)只使用常量额外空间（不考虑排序空间）

相关题目