Welcome to Subscribe On Youtube
3169. Count Days Without Meetings
Description
You are given a positive integer days
representing the total number of days an employee is available for work (starting from day 1). You are also given a 2D array meetings
of size n
where, meetings[i] = [start_i, end_i]
represents the starting and ending days of meeting i
(inclusive).
Return the count of days when the employee is available for work but no meetings are scheduled.
Note: The meetings may overlap.
Example 1:
Input: days = 10, meetings = [[5,7],[1,3],[9,10]]
Output: 2
Explanation:
There is no meeting scheduled on the 4^{th} and 8^{th} days.
Example 2:
Input: days = 5, meetings = [[2,4],[1,3]]
Output: 1
Explanation:
There is no meeting scheduled on the 5^{th }day.
Example 3:
Input: days = 6, meetings = [[1,6]]
Output: 0
Explanation:
Meetings are scheduled for all working days.
Constraints:
1 <= days <= 10^{9}
1 <= meetings.length <= 10^{5}
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days
Solutions
Solution 1: Sorting
We can sort all the meetings by their start time, and use a variable last
to record the latest end time of the previous meetings.
Then we traverse all the meetings. For each meeting $(st, ed)$, if last < st
, it means that the time period from last
to st
is a time period when employees can work and no meetings are scheduled. We add this time period to the answer. Then we update last = max(last, ed)
.
Finally, if last < days
, it means that there is a time period after the end of the last meeting when employees can work and no meetings are scheduled. We add this time period to the answer.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Where $n$ is the number of meetings.

class Solution { public int countDays(int days, int[][] meetings) { Arrays.sort(meetings, (a, b) > a[0]  b[0]); int ans = 0, last = 0; for (var e : meetings) { int st = e[0], ed = e[1]; if (last < st) { ans += st  last  1; } last = Math.max(last, ed); } ans += days  last; return ans; } }

class Solution { public: int countDays(int days, vector<vector<int>>& meetings) { sort(meetings.begin(), meetings.end()); int ans = 0, last = 0; for (auto& e : meetings) { int st = e[0], ed = e[1]; if (last < st) { ans += st  last  1; } last = max(last, ed); } ans += days  last; return ans; } };

class Solution: def countDays(self, days: int, meetings: List[List[int]]) > int: meetings.sort() ans = last = 0 for st, ed in meetings: if last < st: ans += st  last  1 last = max(last, ed) ans += days  last return ans

func countDays(days int, meetings [][]int) (ans int) { sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] }) last := 0 for _, e := range meetings { st, ed := e[0], e[1] if last < st { ans += st  last  1 } last = max(last, ed) } ans += days  last return }

function countDays(days: number, meetings: number[][]): number { meetings.sort((a, b) => a[0]  b[0]); let [ans, last] = [0, 0]; for (const [st, ed] of meetings) { if (last < st) { ans += st  last  1; } last = Math.max(last, ed); } ans += days  last; return ans; }