Skip to content

← leetcode

Count Days Without Meetings

· Medium

LeetCode problem 3169

You start off the algorithm by sorting the meetings from smallest to largest.

Next, we keep track of the maximum meetings[i][1] value with prev, as that tells us when the previous meeting ends. Then, when we iterate through meetings, we check if meetings[i][0] > prev + 1:

  • if the inequality is true, then that implies that there are meetings[i][0] - prev - 1 days where the employee is available for work but no meetings are scheduled
  • if the inequality is false, then that implies that both meeting times overlap, so for that specific instance, there does not exist any days where the employee is available for work with no meetings scheduled

Finally, we just simply sum up these values into ans and return it.

code

class Solution {
public:
    int countDays(int days, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        meetings.push_back({days+1, days+1});
        int ans = 0;
        int prev = 0;
        for (int i = 0; i < meetings.size(); ++i) {
            if (meetings[i][0] - prev - 1 > 0) {
                ans += meetings[i][0] - prev - 1;
            }
            prev = max(prev, meetings[i][1]);
        }

        return ans;
    }
};

complexity

  • Time: O(n log(n))
  • Space: O(1)