Count Days Without Meetings
Problem
An employee works for days consecutive days, numbered 1 to days. A list of meetings is scheduled, where each meeting [start, end] occupies every day from start to end inclusive (1 ≤ start ≤ end ≤ days), and meetings may overlap each other.
Return how many of the days work days have no meeting scheduled at all.
days = 10, meetings = [[5,7],[1,3],[9,10]]2def count_days(days, meetings):
meetings.sort()
covered = 0
cur_end = 0
for start, end in meetings:
if start > cur_end:
covered += end - start + 1
cur_end = end
elif end > cur_end:
covered += end - cur_end
cur_end = end
return days - coveredfunction countDays(days, meetings) {
meetings.sort((a, b) => a[0] - b[0]);
let covered = 0, curEnd = 0;
for (const [start, end] of meetings) {
if (start > curEnd) {
covered += end - start + 1;
curEnd = end;
} else if (end > curEnd) {
covered += end - curEnd;
curEnd = end;
}
}
return days - covered;
}int countDays(int days, int[][] meetings) {
Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
int covered = 0, curEnd = 0;
for (int[] m : meetings) {
if (m[0] > curEnd) {
covered += m[1] - m[0] + 1;
curEnd = m[1];
} else if (m[1] > curEnd) {
covered += m[1] - curEnd;
curEnd = m[1];
}
}
return days - covered;
}int countDays(int days, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
int covered = 0, curEnd = 0;
for (auto& m : meetings) {
if (m[0] > curEnd) {
covered += m[1] - m[0] + 1;
curEnd = m[1];
} else if (m[1] > curEnd) {
covered += m[1] - curEnd;
curEnd = m[1];
}
}
return days - covered;
}Explanation
Checking every single day against every meeting would be far too slow when days is huge. The key insight is to flip the question: free days = days − covered days, where the covered count is the size of the union of all meeting intervals. So the whole problem reduces to measuring a union of intervals without double-counting overlaps.
Sorting the meetings by start day makes the union easy to measure with a single sweep. We keep cur_end, the latest day covered by everything processed so far. Each new meeting [start, end] falls into one of three cases: it starts after cur_end (a brand-new block, all end − start + 1 days are new), it overlaps the current block but pokes past it (only the tail end − cur_end days are new), or it sits entirely inside what is already covered (nothing new).
Walking the default example, days = 10 with meetings sorted to [1,3], [5,7], [9,10]: meeting [1,3] starts a block, covered = 3 and cur_end = 3. Meeting [5,7] starts past cur_end (day 4 stays free), covered = 6 and cur_end = 7. Meeting [9,10] again starts past cur_end (day 8 stays free), covered = 8 and cur_end = 10.
Finally the answer is 10 − 8 = 2 free days. Note we never list the free days; we only count them, which is why the running total is all the state we need.
Correctness relies on the sort: because meetings arrive in increasing start order, any meeting with start ≤ cur_end must overlap the most recent merged block, so adding only the part beyond cur_end counts each calendar day exactly once.
The sort costs O(n log n) and the sweep is a single O(n) pass with a constant number of variables, so the total time is O(n log n) with O(1) extra space. Crucially, the running time depends only on the number of meetings, never on days.