2025-01-06：无需开会的工作日。用go语言，给定一个正整数 days，表示员工可以工作的总天数（从第 1 天开始）。

同时还有一个二维数组 meetings，其长度为 n，其中每个元素 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含这两天）。

请计算员工可以工作的天数，这些天数在所有安排的会议时间之外，且要考虑会议时间可能的重叠情况。

1 <= days <= 1000000000。

1 <= meetings.length <= 100000。

meetings[i].length == 2。

1 <= meetings[i][0] <= meetings[i][1] <= days。

输入：days = 10, meetings = [[5,7],[1,3],[9,10]]。

输出：2。

解释：

第 4 天和第 8 天没有安排会议。

答案2025-01-06：

chatgpt[1]

题目来自leetcode3169。

大体步骤如下：

1.首先，引入必要的包并定义主函数 main 和求解函数 countDays。

2.在 countDays 函数中，首先对会议时间表按照会议开始时间进行排序，以便后续处理时能够按顺序遍历。

3.初始化当前合并区间的左右端点 start 和 end。

4.遍历会议时间表 meetings，对于每一个会议时间段 p：

• 如果该会议的开始时间 p[0] 大于当前合并区间的结束时间 end，说明 p 和当前合并区间不相交，需要把不相交的天数减去，更新新的合并区间的起始位置为 p[0]。• 更新当前合并区间的结束时间为 max(end, p[1])。

5.处理最后一个合并区间，将最后一个合并区间的长度减去。

6.返回最终的结果。

总的时间复杂度取决于排序时间和遍历 meetings 的时间，在最坏情况下时间复杂度为O(n log n)。

额外空间复杂度主要取决于排序和一些变量的存储，为O(n)。

Go完整代码如下：package mainimport ( "fmt" "slices")func countDays(days int, meetings [][]int) int { slices.SortFunc(meetings, func(p, q []int) int { return p[0] - q[0] }) // 按照左端点从小到大排序 start, end := 1, 0 // 当前合并区间的左右端点 for _, p := range meetings { if p[0] > end { // 不相交 days -= end - start + 1 // 当前合并区间的长度 start = p[0] // 下一个合并区间的左端点 } end = max(end, p[1]) } days -= end - start + 1 // 最后一个合并区间的长度 return days}func main() { days := 10 meetings := [][]int{{5,7},{1,3},{9,10}} result := countDays(days,meetings) fmt.Println(result)}

Rust完整代码如下：fn count_days(mut days: i32, meetings: &mut Vec<Vec<i32>>) -> i32 { // 按照左端点从小到大排序 meetings.sort_by_key(|meeting| meeting[0]); let mut start = 1; // 当前合并区间的左端点 let mut end = 0; // 当前合并区间的右端点 for meeting in meetings { if meeting[0] > end { // 不相交 days -= end - start + 1; // 当前合并区间的长度 start = meeting[0]; // 下一个合并区间的左端点 } end = end.max(meeting[1]); // 更新当前合并区间的右端点 } days -= end - start + 1; // 最后一个合并区间的长度 days}fn main() { let days = 10; let mut meetings = vec![vec![5, 7], vec![1, 3], vec![9, 10]]; let result = count_days(days, &mut meetings); println!("{}", result);}

C完整代码如下：#include <stdio.h>#include <stdlib.h>// 比较函数用于 qsortint compare(const void *a, const void *b) { int *meetingA = (int *)a; int *meetingB = (int *)b; return meetingA[0] - meetingB[0]; // 按照左端点排序}int countDays(int days, int meetings[][2], int meetingCount) { // 排序会议 qsort(meetings, meetingCount, sizeof(meetings[0]), compare); int start = 1, end = 0; // 当前合并区间的左右端点 for (int i = 0; i < meetingCount; i++) { int *p = meetings[i]; if (p[0] > end) { // 不相交 days -= end - start + 1; // 当前合并区间的长度 start = p[0]; // 下一个合并区间的左端点 } if (end < p[1]) { end = p[1]; // 更新当前合并区间的右端点 } } days -= end - start + 1; // 最后一个合并区间的长度 return days;}int main() { int days = 10; int meetings[3][2] = {{5, 7}, {1, 3}, {9, 10}}; // 会议数组 int result = countDays(days, meetings, 3); // 传入会议数量 printf("%d\n", result); return 0;}

C++完整代码如下：#include <iostream>#include <vector>#include <algorithm>int countDays(int days, std::vector<std::vector<int>>& meetings) { // 按照左端点从小到大排序 std::sort(meetings.begin(), meetings.end()); int start = 1, end = 0; // 当前合并区间的左右端点 for (const auto& p : meetings) { if (p[0] > end) { // 不相交 days -= (end - start + 1); // 当前合并区间的长度 start = p[0]; // 下一个合并区间的左端点 } end = std::max(end, p[1]); // 更新当前合并区间的右端点 } days -= (end - start + 1); // 最后一个合并区间的长度 return days;}int main() { int days = 10; std::vector<std::vector<int>> meetings = {{5, 7}, {1, 3}, {9, 10}}; int result = countDays(days, meetings); std::cout << result << std::endl; return 0;}

Python完整代码如下：# -*-coding:utf-8-*-def count_days(days, meetings): # 按照左端点从小到大排序 meetings.sort(key=lambda x: x[0]) start, end = 1, 0 # 当前合并区间的左右端点 for p in meetings: if p[0] > end: # 不相交 days -= end - start + 1 # 当前合并区间的长度 start = p[0] # 下一个合并区间的左端点 end = max(end, p[1]) # 更新当前合并区间的右端点 days -= end - start + 1 # 最后一个合并区间的长度 return days# 主函数if __name__ == '__main__': days = 10 meetings = [[5, 7], [1, 3], [9, 10]] result = count_days(days, meetings) print(result)

Bash完整代码如下：#!/bin/bashcount_days() { local days=$1 shift local meetings=("$@") # 按照左端点从小到大排序 IFS=$'\n' sorted=($(sort -n <<<"${meetings[*]}")) unset IFS local start=1 local end=0 for meeting in "${sorted[@]}"; do local p=(${meeting//,/ }) # 将字符串分割成数组 local start_meeting=${p[0]} local end_meeting=${p[1]} if (( start_meeting > end )); then # 不相交 (( days -= end - start + 1 )) # 当前合并区间的长度 start=$start_meeting # 下一个合并区间的左端点 fi end=$(( end > end_meeting ? end : end_meeting )) # 更新当前合并区间的右端点 done (( days -= end - start + 1 )) # 最后一个合并区间的长度 echo $days}# 主程序days=10meetings=("5,7" "1,3" "9,10") # 会议阵列result=$(count_days $days "${meetings[@]}")echo "$result"

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP