Watch 10 video solutions for Count Days Without Meetings, a medium level problem involving Array, Sorting. This walkthrough by NeetCodeIO has 9,431 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |