普通视图

发现新文章,点击刷新页面。
昨天以前首页

排序

作者 tsreaper
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;
    }
};
❌
❌