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.

Description Hints 2 Solution Video 14:32

3169. Count Days Without Meetings

Medium48.1% acceptance4 companies

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 4^th and 8^th days.

Example 2:

Input: days = 5, meetings = [[2,4],[1,3]]

Output: 1

Explanation:

There is no meeting scheduled on the 5^thday.

Example 3:

Input: days = 6, meetings = [[1,6]]

Output: 0

Explanation:

Meetings are scheduled for all working days.

Constraints:

1 <= days <= 10⁹
1 <= meetings.length <= 10⁵
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days

Asked at 4 companies

Swiggy

Google Microsoft Amazon

Topics

Array Sorting

Hints open one at a time

Hint 1

Merge the overlapping meetings and sort the new meetings timings.

Hint 2

Return the sum of difference between the end time of a meeting and the start time of the next meeting for all adjacent pairs.

14:32

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

3169. Count Days Without Meetings

Asked at 4 companies

Topics

Hints open one at a time

Similar problems