排序
2024年6月2日 12:20
解法:排序
区间并模板题。答案就是 days
减去区间并的长度之和。区间并详见 leetcode 56. 合并区间。
复杂度 $\mathcal{O}(n\log n)$,主要是给区间排序的复杂度。
参考代码(c++)
###cpp
class Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
int ans = 0;
int R = 0;
for (auto &meet : meetings) {
if (meet[0] > R) ans += meet[0] - R - 1;
R = max(R, meet[1]);
}
ans += days - R;
return ans;
}
};