3169.无需开会的工作日：排序+一次遍历——不需要正难则反，因为正着根本不难

【LetMeFly】3169.无需开会的工作日：排序+一次遍历——不需要正难则反，因为正着根本不难

力扣题目链接：https://leetcode.cn/problems/count-days-without-meetings/

给你一个正整数 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

好奇，怎么都在说正难则反。

解题方法：排序

只需要按照meetings开始的顺序从小到大排序，使用一个变量(last)记录上次会议的结束日期（初始值为0），接着开始遍历meetings数组。

如果开始时间比last晚不只一天，就说明从last到这个开始时间都有空，累加到答案中。每遍历完一个meeting，就将last更新为last和meeting结束时间的最大值。

最终，days-last也是空闲时间，累加到答案中。

• 时间复杂度$O(n\log n)$，其中$n=len(meetings)$。
• 空间复杂度$O(\log n)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-07-11 23:25:31
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-11 23:33:35
 */
class Solution {
public:
    int countDays(int days, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        int ans = 0;
        int last = 0;
        for (vector<int> me : meetings) {
            // printf("last = %d, me = [%d, %d]\n", last, me[0], me[1]);
            if (me[0] > last + 1) {
                ans += me[0] - last - 1;
                // printf("ans += %d\n", me[0] - last - 1);
            }
            last = max(last, me[1]);
        }
        ans += days - last;
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-07-11 23:25:31
LastEditors: LetMeFly.xyz
LastEditTime: 2025-07-12 12:00:22
'''
from typing import List

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        ans = last = 0
        meetings.sort()
        for l, r in meetings:
            if l > last + 1:
                ans += l - last - 1
            last = max(last, r)
        ans += days - last
        return ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-07-11 23:25:31
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-12 16:58:44
 */
import java.util.Arrays;

class Solution {
    public int countDays(int days, int[][] meetings) {
        int ans = 0;
        int last = 0;
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        for (int[] me : meetings) {
            if (me[0] > last + 1) {
                ans += me[0] - last - 1;
            }
            last = Math.max(last, me[1]);
        }
        ans += days - last;
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-07-11 23:25:31
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-12 17:00:47
 */
package main

import "slices"

func countDays(days int, meetings [][]int) (ans int) {
    last := 0
    slices.SortFunc(meetings, func(a, b []int) int {return a[0] - b[0]})
    for _, me := range meetings {
        if me[0] > last + 1 {
            ans += me[0] - last - 1
        }
        last = max(last, me[1])
    }
    ans += days - last
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源