Count Days Without Meetings
Count Days Without Meetings is a medium intervals problem solved with the basics pattern.
The best approach, optimal (sort and sweep merged blocks), runs in O(m log m) time and O(log m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (mark every day) up.
Problem
An employee is available for days days, numbered from 1 to days. You are also given meetings, where meetings[i] = [start_i, end_i] means a meeting occupies every day from start_i to end_i, both included.
Meetings may overlap. Return how many days in the range 1..days have no meeting scheduled at all.
Examples
Example 1
- Input
days = 8, meetings = [[2, 3], [6, 7], [3, 4]]- Output
3- Why
- Days 2, 3, 4, 6 and 7 are busy, so days 1, 5 and 8 are free.
Example 2
- Input
days = 5, meetings = [[1, 5]]- Output
0- Why
- A single meeting covers the whole period.
Example 3
- Input
days = 7, meetings = [[4, 4], [2, 2]]- Output
5- Why
- Only days 2 and 4 are busy; days 1, 3, 5, 6 and 7 are free.
Constraints
1 <= days <= 10^91 <= meetings.length <= 10^5meetings[i] = [start_i, end_i]with1 <= start_i <= end_i <= days
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (mark every day) | O(days + total meeting length) | O(days) |
| Optimal (sort and sweep merged blocks) | O(m log m) | O(log m) |
1Brute force (mark every day)
O(days + total meeting length)Each meeting walks over all its days, and the final count walks over every day.O(days)One flag per day; impossible when days is 10^9.Keep one flag per day. For every meeting, mark each day in its range as busy. Then count the days that were never marked.
- Create a boolean array busy of size days + 1.
- For each meeting [s, e], set busy[d] = true for d from s to e.
- Count d in 1..days with busy[d] == false.
class Solution {
public int countDays(int days, int[][] meetings) {
boolean[] busy = new boolean[days + 1];
for (int[] m : meetings) {
for (int d = m[0]; d <= m[1]; d++) {
busy[d] = true;
}
}
int free = 0;
for (int d = 1; d <= days; d++) {
if (!busy[d]) free++;
}
return free;
}
}class Solution:
def countDays(self, days: int, meetings: List[List[int]]) -> int:
busy = bytearray(days + 1)
for s, e in meetings:
for d in range(s, e + 1):
busy[d] = 1
return days - sum(busy)class Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
vector<bool> busy(days + 1, false);
for (auto& m : meetings) {
for (int d = m[0]; d <= m[1]; d++) {
busy[d] = true;
}
}
int free = 0;
for (int d = 1; d <= days; d++) {
if (!busy[d]) free++;
}
return free;
}
};function countDays(days, meetings) {
const busy = new Uint8Array(days + 1);
for (const [s, e] of meetings) {
for (let d = s; d <= e; d++) {
busy[d] = 1;
}
}
let free = 0;
for (let d = 1; d <= days; d++) {
if (!busy[d]) free++;
}
return free;
}2Optimal (sort and sweep merged blocks)
O(m log m)Sorting the m meetings dominates; the sweep is linear.O(log m)Only the sort's internal stack; the sweep uses two variables.Sort the meetings by start day and sweep them while remembering lastEnd, the latest busy day so far. If a meeting starts after lastEnd + 1, the days strictly between are free. Extending lastEnd with max merges overlapping and nested meetings automatically. At the end, the days after lastEnd are free too.
- Sort meetings by start.
- Set lastEnd = 0 and free = 0.
- For each [s, e]: if s > lastEnd + 1, add s - lastEnd - 1 to free; then lastEnd = max(lastEnd, e).
- Add days - lastEnd to free and return it.
class Solution {
public int countDays(int days, int[][] meetings) {
Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
int lastEnd = 0;
int free = 0;
for (int[] m : meetings) {
if (m[0] > lastEnd + 1) {
free += m[0] - lastEnd - 1;
}
lastEnd = Math.max(lastEnd, m[1]);
}
free += days - lastEnd;
return free;
}
}class Solution:
def countDays(self, days: int, meetings: List[List[int]]) -> int:
meetings.sort(key=lambda m: m[0])
last_end = 0
free = 0
for s, e in meetings:
if s > last_end + 1:
free += s - last_end - 1
last_end = max(last_end, e)
free += days - last_end
return freeclass Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end(),
[](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
int lastEnd = 0;
int free = 0;
for (auto& m : meetings) {
if (m[0] > lastEnd + 1) {
free += m[0] - lastEnd - 1;
}
lastEnd = max(lastEnd, m[1]);
}
free += days - lastEnd;
return free;
}
};function countDays(days, meetings) {
meetings.sort((a, b) => a[0] - b[0]);
let lastEnd = 0;
let free = 0;
for (const [s, e] of meetings) {
if (s > lastEnd + 1) {
free += s - lastEnd - 1;
}
lastEnd = Math.max(lastEnd, e);
}
free += days - lastEnd;
return free;
}Edge cases to test
- Overlapping meetings must not be subtracted twice
- Meetings that touch end to start, like [1, 3] and [4, 6], leave no free day between them
- One meeting nested inside another
- Free days before the first meeting and after the last one
- days is huge (10^9), so you cannot keep one flag per day
Hints
Hint 1
Overlaps are the hard part. What happens if you first merge overlapping meetings into disjoint blocks?
Hint 2
Sort meetings by start day and keep the latest end day seen so far.
Hint 3
A gap exists when a meeting starts more than one day after that latest end; also count the days after the final end.
FAQ
What is the best time complexity for Count Days Without Meetings?
Optimal (sort and sweep merged blocks) runs in O(m log m) time and O(log m) extra space. Sorting the m meetings dominates; the sweep is linear.
Which pattern does Count Days Without Meetings use?
It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.
Is there a brute force solution for Count Days Without Meetings?
Yes. Brute force (mark every day) takes O(days + total meeting length) time and O(days) space. Keep one flag per day.
Which edge cases should I test for Count Days Without Meetings?
Overlapping meetings must not be subtracted twice; Meetings that touch end to start, like [1, 3] and [4, 6], leave no free day between them; One meeting nested inside another; Free days before the first meeting and after the last one; days is huge (10^9), so you cannot keep one flag per day.