class Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
}
};
3169. 无需开会的工作日
给你一个正整数 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 <= 1091 <= meetings.length <= 105meetings[i].length == 21 <= meetings[i][0] <= meetings[i][1] <= days相似题目
原站题解
php 解法, 执行用时: 831 ms, 内存消耗: 93.4 MB, 提交时间: 2024-06-04 10:00:48
class Solution {
/**
* @param Integer $days
* @param Integer[][] $meetings
* @return Integer
*/
function countDays($days, $meetings) {
uasort($meetings, function($v1, $v2) {
if ($v1[0] == $v2[0] ) return 0;
return ($v1[0] < $v2[0]) ? -1 : 1;
});
$start = 1;
$end = 0;
foreach ( $meetings as $m ) {
list($s, $e) = $m;
if ( $s > $end ) { # 不相交
$days -= $end - $start + 1; # 当前合并区间的长度
$start = $s; # 下一个合并区间的左端点
}
$end = max($end, $e);
}
$days -= $end - $start + 1; # 最后一个合并区间的长度
return $days;
}
}
cpp 解法, 执行用时: 359 ms, 内存消耗: 122.7 MB, 提交时间: 2024-06-04 09:53:38
class Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
ranges::sort(meetings); // 按照左端点从小到大排序
int start = 1, end = 0; // 当前合并区间的左右端点
for (auto& p : meetings) {
if (p[0] > end) { // 不相交
days -= end - start + 1; // 当前合并区间的长度
start = p[0]; // 下一个合并区间的左端点
}
end = max(end, p[1]);
}
days -= end - start + 1; // 最后一个合并区间的长度
return days;
}
};
java 解法, 执行用时: 38 ms, 内存消耗: 98.2 MB, 提交时间: 2024-06-04 09:53:14
class Solution {
public int countDays(int days, int[][] meetings) {
Arrays.sort(meetings, (p, q) -> p[0] - q[0]); // 按照左端点从小到大排序
int start = 1, end = 0; // 当前合并区间的左右端点
for (int[] p : meetings) {
if (p[0] > end) { // 不相交
days -= end - start + 1; // 当前合并区间的长度
start = p[0]; // 下一个合并区间的左端点
}
end = Math.max(end, p[1]);
}
days -= end - start + 1; // 最后一个合并区间的长度
return days;
}
}
rust 解法, 执行用时: 72 ms, 内存消耗: 9.4 MB, 提交时间: 2024-06-04 09:52:48
use std::cmp::max;
impl Solution {
pub fn count_days(days: i32, meetings: Vec<Vec<i32>>) -> i32 {
let mut meetings = meetings;
let mut days = days;
meetings.sort_by(|v1, v2| v1[0].cmp(&v2[0]));
let mut start = 1;
let mut end = 0;
for v in meetings.iter() {
if v[0] > end {
days -= end - start + 1;
start = v[0];
}
end = max(end, v[1]);
}
days - (end - start + 1)
}
}
golang 解法, 执行用时: 186 ms, 内存消耗: 17.1 MB, 提交时间: 2024-06-04 09:52:33
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
}
python3 解法, 执行用时: 214 ms, 内存消耗: 50.8 MB, 提交时间: 2024-06-04 09:52:09
class Solution:
def countDays(self, days: int, meetings: List[List[int]]) -> int:
meetings.sort(key=lambda p: p[0]) # 按照左端点从小到大排序
start, end = 1, 0 # 当前合并区间的左右端点
for s, e in meetings:
if s > end: # 不相交
days -= end - start + 1 # 当前合并区间的长度
start = s # 下一个合并区间的左端点
end = max(end, e)
days -= end - start + 1 # 最后一个合并区间的长度
return days