Count Days Without Meetings — Solution in Python, Java & C++
Count Days Without Meetings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Days Without Meetings is a medium coding problem on arrays and sorting, asked in Amazon, Google and Salesforce interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting
- Asked at: Amazon, Google, Salesforce
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An employee is available for work on days 1 through days. meetings[i] = [start, end] is a meeting spanning those days inclusive; meetings may overlap.
Return the number of days with no meeting scheduled.
Example 1
Input: days = 10, meetings = [[5,7],[1,3],[9,10]]
Output: 2
Explanation: Days 4 and 8 are free.
Example 2
Input: days = 5, meetings = [[2,4],[1,3]]
Output: 1
Explanation: The two meetings cover days 1 to 4.
Example 3
Input: days = 6, meetings = [[1,6]]
Output: 0
Constraints
1 <= days <= 10^91 <= meetings.length <= 10^5meetings[i].length == 21 <= meetings[i][0] <= meetings[i][1] <= days
Hints for Count Days Without Meetings
Hint 1
dayscan be a billion, so the free days cannot be marked one by one.Hint 2
Sort by start and sweep, tracking the furthest day covered so far.
Hint 3
Count covered days, then subtract from
days.
How to solve Count Days Without Meetings
Sort the meetings by start and sweep, keeping reach — the furthest day covered so far. Each meeting adds only the part beyond reach, so the total covered count is exact even with overlaps.
Approach
- Sort the meetings by start day.
- For each, start counting from
max(start, reach + 1). - If that is at most the meeting's end, add the span and advance
reach. - Return
days - covered.
Why it works
Clamping each meeting's start to reach + 1 is what makes overlapping and fully-nested meetings harmless — the overlap is simply not counted twice, and a meeting entirely inside an earlier one contributes nothing. Working with counts rather than a day-by-day array is what keeps this feasible at days = 10^9.
Complexity
- Time —
O(m log m) - Space —
O(m)
Pitfalls
- Marking each day individually is impossible at
10^9. - A meeting contained in an earlier one must add zero, not its full length.
- Both endpoints are inclusive, so a meeting
[x, x]covers one day.
Reference solution
Python
from typing import List
def countDays(days: int, meetings: List[List[int]]) -> int:
covered = 0
reach = 0
for start, end in sorted(meetings):
s = max(start, reach + 1)
if end >= s:
covered += end - s + 1
reach = end
return days - coveredJava
public static int countDays(int days, int[][] meetings) {
int[][] sorted = meetings.clone();
Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
long covered = 0;
int reach = 0;
for (int[] m : sorted) {
int s = Math.max(m[0], reach + 1);
if (m[1] >= s) {
covered += m[1] - s + 1;
reach = m[1];
}
}
return (int) (days - covered);
}C++
int countDays(int days, vector<vector<int>>& meetings) {
vector<vector<int>> sorted = meetings;
sort(sorted.begin(), sorted.end());
long long covered = 0;
int reach = 0;
for (auto& m : sorted) {
int s = max(m[0], reach + 1);
if (m[1] >= s) {
covered += m[1] - s + 1;
reach = m[1];
}
}
return (int) (days - covered);
}JavaScript
var countDays = function(days, meetings) {
var sorted = meetings.slice();
sorted.sort(function(a, b) { return a[0] - b[0]; });
var covered = 0, reach = 0;
for (var i = 0; i < sorted.length; i++) {
var s = sorted[i][0] > reach + 1 ? sorted[i][0] : reach + 1;
if (sorted[i][1] >= s) {
covered += sorted[i][1] - s + 1;
reach = sorted[i][1];
}
}
return days - covered;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms