Skip to main content
Talentd

Count Days Without Meetings - Solution & Explanation

MediumArraySorting12 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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 <= 109
  • 1 <= meetings.length <= 105
  • meetings[i].length == 2
  • 1 <= meetings[i][0] <= meetings[i][1] <= days

Approach Overview

Problem 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 1: Boolean Array Approach

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Optimized Range Counting

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n + days) where n is the number of meetings.
Space Complexity: O(days) for the auxiliary array used for interval counting.

Try this approach in the editor →

Approach 3: Sorting

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(days), where `days` is the size of the boolean array.

Optimized Range Counting

Time Complexity: O(n + days) where n is the number of meetings.
Space Complexity: O(days) for the auxiliary array used for interval counting.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Boolean Array ApproachO(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

Video Solution

Count Days Without Meetings - Leetcode 3169 - Python • NeetCodeIO • 9,532 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Days Without Meetings easy or hard?
The problem is rated Medium because it requires recognizing the interval merging pattern. The logic itself is straightforward once you identify that overlapping meeting ranges should be combined before counting occupied days.
Count Days Without Meetings Python/Java solution
Python and Java implementations typically follow the same pattern: sort the intervals by start day, merge overlapping ranges while counting covered days, and subtract that from the total days. The boolean array alternative is easier to implement but less memory efficient.
How to solve Count Days Without Meetings in O(n)?
An O(n) pass is possible after sorting the intervals. First sort the meetings by start day, then iterate once to merge overlapping intervals and accumulate the number of covered days. The counting step itself is linear, while the full algorithm remains O(m log m) due to the sorting step.
What is the best approach for Count Days Without Meetings?
The most efficient solution sorts meeting intervals and merges overlapping ranges before counting covered days. This interval merging approach runs in O(m log m) time due to sorting and O(1) additional space if merging in place. After calculating total occupied days, subtract that value from the total number of days.
Is Count Days Without Meetings asked at Google/Amazon/Meta?
Interval merging and calendar scheduling problems are common at companies like Google, Amazon, and Meta. Variations of this problem appear in interview rounds where candidates must process overlapping intervals efficiently using sorting and linear scanning.
What data structure is used in Count Days Without Meetings?
The problem mainly uses arrays to store meeting intervals and relies on sorting plus interval merging. Some straightforward implementations also use a boolean array to mark occupied days, but optimized solutions operate directly on sorted interval ranges.
What is the time complexity of Count Days Without Meetings?
The optimized solution runs in O(m log m) time where m is the number of meetings, because the intervals must be sorted before merging. The merge pass itself is linear. A simpler boolean array simulation runs in O(days + m) time but uses O(days) memory.

Ready to solve this problem?

Practice Count Days Without Meetings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Merge Intervals