跳转至

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

解法

方法一：排序

我们不妨将所有会议按照开始时间排序，用一个变量 \(\textit{last}\) 记录此前会议的最晚结束时间。

然后我们遍历所有会议，对于每一个会议 \((\textit{st}, \textit{ed})\)，如果 \(\textit{last} < \textit{st}\)，说明 \(\textit{last}\) 到 \(\textit{st}\) 之间的时间段是员工可以工作且没有安排会议的时间，我们将这段时间加入答案。然后我们更新 \(\textit{last} = \max(\textit{last}, \textit{ed})\)。

最后，如果 \(\textit{last} < \textit{days}\)，说明最后一次会议结束后还有时间段是员工可以工作且没有安排会议的时间，我们将这段时间加入答案。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 为会议的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        ans = last = 0
        for st, ed in meetings:
            if last < st:
                ans += st - last - 1
            last = max(last, ed)
        ans += days - last
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        int ans = 0, last = 0;
        for (var e : meetings) {
            int st = e[0], ed = e[1];
            if (last < st) {
                ans += st - last - 1;
            }
            last = Math.max(last, ed);
        }
        ans += days - last;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int countDays(int days, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        int ans = 0, last = 0;
        for (auto& e : meetings) {
            int st = e[0], ed = e[1];
            if (last < st) {
                ans += st - last - 1;
            }
            last = max(last, ed);
        }
        ans += days - last;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func countDays(days int, meetings [][]int) (ans int) {
    sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
    last := 0
    for _, e := range meetings {
        st, ed := e[0], e[1]
        if last < st {
            ans += st - last - 1
        }
        last = max(last, ed)
    }
    ans += days - last
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function countDays(days: number, meetings: number[][]): number {
    meetings.sort((a, b) => a[0] - b[0]);
    let [ans, last] = [0, 0];
    for (const [st, ed] of meetings) {
        if (last < st) {
            ans += st - last - 1;
        }
        last = Math.max(last, ed);
    }
    ans += days - last;
    return ans;
}

评论