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] <= daysThis 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.
C++
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.
Java
Time Complexity: O(n + days) where n is the number of meetings.
Space Complexity: O(days) for the auxiliary array used for interval counting.
| 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. |
Count Days Without Meetings - Leetcode 3169 - Python • NeetCodeIO • 8,273 views views
Watch 9 more video solutions →Practice Count Days Without Meetings with our built-in code editor and test cases.
Practice on FleetCode