3169、无须开会的工作日

leetcode 排序区间合并

发布时间 : 2025-07-13 07:24

字数:580 阅读 :

评论:

题目
题解
1. 分析
2. 代码

题目

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

题解

分析

问题本质：区间合并题。

代码

Python 版实现 —— ai生成


class Solution(object):
    def countDays(self, days, meetings):
        if not meetings:
            return days

        # 1. 按开始时间排序会议
        meetings.sort()

        # 2. 合并重叠的会议区间
        merged_meetings = []
        for start, end in meetings:
            if not merged_meetings or start > merged_meetings[-1][1]:
                # 如果合并列表为空，或者当前会议与最后一个合并区间不重叠
                merged_meetings.append([start, end])
            else:
                # 如果重叠，更新最后一个合并区间的结束时间
                merged_meetings[-1][1] = max(merged_meetings[-1][1], end)

        # 3. 计算合并区间占据的总天数
        occupied_days = 0
        for start, end in merged_meetings:
            # 确保区间在总天数范围内
            actual_start = max(1, start)
            actual_end = min(days, end)
            if actual_start <= actual_end:
                occupied_days += (actual_end - actual_start + 1)

        # 4. 计算可工作天数
        return days - occupied_days

Java 实现

class Solution {
    public int countDays(int days, int[][] meetings) {
               // 1、按照开始时间排序会议 从小到大排序
        Arrays.sort(meetings, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        }
        );

        // 2、合并重叠的会议区间
        List<int[]> merged = new ArrayList<>();

        for (int[] interval : meetings) {
            if (merged.isEmpty() || interval[0] > merged.get(merged.size() - 1)[1]) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        // 3、计算合并区间的总天数
        int meetingDatsCount = 0;
        for (int[] interval : merged) {
            int start = Math.max(1, interval[0]);
            int end = Math.min(days, interval[1]);
            if (start <= end) {
                meetingDatsCount += end - start + 1;
            }

        }
        // 4、计算剩余天数
        return days - meetingDatsCount;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com