How does sorting help solve the Count Days Without Meetings problem?

Sorting the meetings ensures that overlapping intervals are adjacent, which simplifies the merging process and reduces the number of operations needed.

What is the time complexity of the solution?

The time complexity is O(N log N) due to sorting the meetings, where N is the number of meetings.

What if no meetings are scheduled?

If no meetings are scheduled, all days are free, so the answer would be equal to the total number of days available for work.

How do you merge overlapping meetings?

By sorting the meetings and checking if the start of the current meeting is within the end of the previous meeting. If so, merge them by updating the end time of the previous meeting.

How can I optimize this problem for large inputs?

The solution can be optimized by sorting the meetings in O(N log N) time, and then iterating through them once to merge and count free days, which ensures efficient handling of large inputs.

#3169

Medium

auto_awesome数组·排序

LeetCode 题解工作台

无需开会的工作日

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

数组排序

题目描述

给你一个正整数 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 <= 10⁹
1 <= meetings.length <= 10⁵
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days

lightbulb

解题思路

方法一：排序

我们不妨将所有会议按照开始时间排序，用一个变量 $\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

11

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

speed

复杂度分析

指标	值
时间	O(N \cdot log(N))
空间	O(\log⁡⁡ N)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain how sorting affects the merging process?
question_mark
How well does the candidate handle large input sizes efficiently?
question_mark
Is the candidate able to handle edge cases, such as no meetings or full-day meetings?

warning

常见陷阱

外企场景

error
Forgetting to merge overlapping meetings before counting the free days.
error
Incorrectly handling edge cases like no free days or all days being booked.
error
Misunderstanding the problem and incorrectly returning the days with meetings instead of without.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if meetings are given in a random order?
arrow_right_alt
How would the solution change if the input days were larger?
arrow_right_alt
What if meetings don't overlap at all?

help

常见问题

外企场景

继续练习

#3186 施咒的最大总伤害 #3194 最小元素和最大元素的最小平均值 #3143 正方形中的最多点数