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

福大大架构师每日一题

发布于 2025-01-07 08:24:10

6900

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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 main

import(
"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:&mutVec<Vec<i32>>)->i32{
// 按照左端点从小到大排序
    meetings.sort_by_key(|meeting| meeting[0]);

letmut start=1;// 当前合并区间的左端点
letmut end=0;// 当前合并区间的右端点

formeetingin meetings {
if meeting[0]> end {// 不相交
            days -= end - start +1;// 当前合并区间的长度
            start = meeting[0];// 下一个合并区间的左端点
}
        end = end.max(meeting[1]);// 更新当前合并区间的右端点
}
    days -= end - start +1;// 最后一个合并区间的长度

    days
}

fnmain(){
letdays=10;
letmut meetings=vec![vec![5,7],vec![1,3],vec![9,10]];
letresult=count_days(days,&mut meetings);
println!("{}", result);
}

C完整代码如下：

#include <stdio.h>
#include <stdlib.h>

// 比较函数用于 qsort
intcompare(const void *a, const void *b){
int*meetingA =(int*)a;
int*meetingB =(int*)b;
return meetingA[0]- meetingB[0];// 按照左端点排序
}

intcountDays(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;
}

intmain(){
int days =10;
int meetings[3][2]={{5,7},{1,3},{9,10}};// 会议数组
int result = countDays(days, meetings,3);// 传入会议数量
printf("%d\n", result);
return0;
}

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(constauto& 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;
return0;
}

Python完整代码如下：

# -*-coding:utf-8-*-

defcount_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/bash

count_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=10
meetings=("5,7""1,3""9,10")# 会议阵列
result=$(count_days $days"${meetings[@]}")
echo "$result"