3169. 无需开会的工作日

🟠   🔖  数组 排序  🔗 力扣 LeetCode

题目

You are given a positive integer days representing the total number of days an employee is available for work (starting from day 1). You are also given a 2D array meetings of size n where, meetings[i] = [start_i, end_i] represents the starting and ending days of meeting i (inclusive).

Return the count of days when the employee is available for work but no meetings are scheduled.

Note: The meetings may overlap.

Example 1:

Input: days = 10, meetings = [[5,7],[1,3],[9,10]]

Output: 2

Explanation:

There is no meeting scheduled on the 4th and 8th days.

Example 2:

Input: days = 5, meetings = [[2,4],[1,3]]

Output: 1

Explanation:

There is no meeting scheduled on the 5th day.

Example 3:

Input: days = 6, meetings = [[1,6]]

Output: 0

Explanation:

Meetings are scheduled for all working days.

Constraints:

• 1 <= days <= 10^9
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

题目大意

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

解题思路

1. 对会议进行排序

   • 按照 开始日期升序 对会议进行排序。

2. 遍历排序后的会议

   • 用 prev 变量记录当前已经占用到的最晚日期。
   • 对于每场会议：
     • 空闲天数 = 当前会议的 start 与 prev 之间的差值（如果存在空闲）。
     • 如果 end 超过 prev，则更新 prev。

3. 处理最后的空闲天数

   • 遍历结束后，若 prev < days，说明最后一段时间还有空闲天数，需将其计入。

复杂度分析

• 时间复杂度：O(m log m)，其中 m 为会议数量。
  • 对 meetings 进行排序的时间复杂度为 O(m log m)；
  • 遍历每个会议的时间复杂度为 O(m)；
  • 因此整体时间复杂度为 O(m log m)。
• 空间复杂度：O(1)，使用常数级别的变量 count 和 prev，排序可在原数组上进行，不需要额外空间。

代码

/**
 * @param {number} days
 * @param {number[][]} meetings
 * @return {number}
 */
var countDays = function (days, meetings) {
	meetings.sort((a, b) => a[0] - b[0]);
	let count = 0;
	let prev = 0;
	for (let i = 0; i < meetings.length; i++) {
		let [start, end] = meetings[i];
		if (start > prev) {
			count += start - prev - 1;
		}
		prev = Math.max(prev, end);
	}
	count += days - prev;
	return count;
};

相关题目

题号	标题	题解	标签	难度	力扣
56	合并区间	[✓]	数组 排序	🟠	🀄️ 🔗