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 <= 1091 <= meetings.length <= 105meetings[i].length == 21 <= meetings[i][0] <= meetings[i][1] <= daysProblem Overview: You are given a total number of days and a list of meeting intervals. Each interval marks a range of days that already have meetings scheduled. The goal is to count how many days remain free after accounting for all meeting ranges.
Approach 1: Boolean Array Approach (O(days + m), Space O(days))
This method simulates the calendar directly. Create a boolean array of size days + 1 where each index represents whether that day has a meeting. Iterate through every meeting interval and mark each covered day as true. After processing all intervals, scan the array and count how many entries remain false. The approach is simple and intuitive, especially if the number of days is relatively small. It uses direct indexing from an array, making lookups constant time.
The downside is memory usage. If days is very large, allocating a boolean array becomes expensive. Also, iterating through every day inside each interval may repeat work when meetings overlap.
Approach 2: Optimized Range Counting (Sorting + Interval Merge) (O(m log m), Space O(1) or O(m))
This approach focuses on counting covered ranges instead of marking individual days. Start by sorting the meeting intervals by their start day using a sorting step. Then iterate through the intervals and merge overlapping or adjacent ranges while tracking the total number of days occupied by meetings.
Maintain a current merged interval. If the next meeting overlaps with it, extend the end boundary. If it does not overlap, add the length of the current interval to the occupied-day count and start a new interval. After processing all meetings, subtract the total occupied days from days to get the number of free days. This technique is a classic interval merging pattern commonly used in array and scheduling problems.
The key insight: overlapping meetings should only count once. Sorting ensures intervals are processed in order, making it easy to merge them and avoid double counting.
Recommended for interviews: Interviewers expect the interval sorting and merge solution. The boolean array approach demonstrates basic problem understanding but does not scale well for large ranges. The optimized range counting approach shows you recognize overlapping intervals and can apply sorting plus linear scanning to compute the result efficiently.
This approach involves using a boolean array to mark the days that have meetings. We'll iterate over the `meetings` array and mark the respective entries in the boolean array as `True` (indicating a meeting is scheduled for that day). Finally, we'll count the number of days that remain `False` (indicating no meeting).
This Python code initializes a boolean list `meetings_days` where each index represents a day, and the value represents whether a meeting is scheduled. For each meeting interval, it marks the respective days as `True` in the array. Then, it counts and returns the number of `False` days, indicating no meeting is scheduled on those days.
Time Complexity: O(n * m) where n is the number of meetings and m is the maximum length of a single meeting interval.
Space Complexity: O(days), where `days` is the size of the boolean array.
Instead of using a potentially large boolean array, this approach involves tracking the count of meeting intervals that cover each day using a prefix sum array. This avoids marking every individual day explicitly for large inputs.
This Python implementation uses the prefix sum concept for efficiently tracking meeting days. By incrementing the start of a meeting interval and decrementing right after the end, it determines intervals with ongoing meetings when summed sequentially. Days with a sum of zero correspond to no meetings.
Time Complexity: O(n + days) where n is the number of meetings.
Space Complexity: O(days) for the auxiliary array used for interval counting.
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.
| Approach | Complexity |
|---|---|
| Boolean Array Approach | Time Complexity: O(n * m) where n is the number of meetings and m is the maximum length of a single meeting interval. |
| Optimized Range Counting | Time Complexity: O(n + days) where n is the number of meetings. |
| Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Boolean Array Approach | O(days + m) | O(days) | When the total number of days is small and simplicity is preferred |
| Optimized Range Counting (Sort + Merge) | O(m log m) | O(1) or O(m) | Best general solution when intervals may overlap and the day range can be large |
Count Days Without Meetings - Leetcode 3169 - Python • NeetCodeIO • 9,431 views views
Watch 9 more video solutions →Practice Count Days Without Meetings with our built-in code editor and test cases.
Practice on FleetCode