# 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 4th and 8th days.

Example 2:

Input: days = 5, meetings = [[2,4],[1,3]]

Output: 1

Explanation:

There is no meeting scheduled on the 5th day.

Example 3:

Input: days = 6, meetings = [[1,6]]

Output: 0

Explanation:

Meetings are scheduled for all working days.

Constraints:

• 1 <= days <= 109
• 1 <= meetings.length <= 105
• 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;
}