【LetMeFly】3169.無需開會的工作日：排序+一次遍歷——不需要正難則反，因為正著根本不難

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

給你一個正整數 days，表示員工可工作的總天數（從第 1 天開始）。另給你一個二維數組 meetings，長度為 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次會議的開始和結束天數（包含首尾）。

返回員工可工作且沒有安排會議的天數。

注意：會議時間可能會有重疊。

?

示例 1：

輸出：2

解釋：

第 4 天和第 8 天沒有安排會議。

示例 2：

輸出：1

解釋：

第 5 天沒有安排會議。

示例 3：

輸出：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 Listclass Solution:def countDays(self, days: int, meetings: List[List[int]]) -> int:ans = last = 0meetings.sort()for l, r in meetings:if l > last + 1:ans += l - last - 1last = max(last, r)ans += days - lastreturn 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 mainimport "slices"func countDays(days int, meetings [][]int) (ans int) {last := 0slices.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 - lastreturn
}

同步發文于CSDN和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

千篇源碼題解已開源