#3169

Medium

LeetCode Problem Workspace

Count Days Without Meetings

Count Days Without Meetings is a problem where you need to count days without scheduled meetings in a given work period.

array sorting

Problem Statement

You are given a positive integer days, which represents the total number of days an employee is available for work (starting from day 1). You are also given a 2D array meetings 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 that the meetings may overlap.

Examples

Example 1

Input: days = 10, meetings = [[5,7],[1,3],[9,10]]

Output: 2

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

There is no meeting scheduled on the 5 th day.

Example 3

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

Output: 0

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

Solution Approach

Sort and Merge Meetings

Sort the meetings by their start day, then merge any overlapping meetings to form a new set of non-overlapping intervals. This reduces the complexity of counting free days.

Count Free Days

After merging the meetings, iterate through the days and count how many days are not included in the merged meeting intervals. This count gives the number of free days.

Handle Edge Cases

Ensure to handle cases where meetings occupy all days or where there are no meetings. These edge cases can affect the result and should be carefully considered.

Complexity Analysis

Metric	Value
Time	O(N \cdot log(N))
Space	O(\log⁡⁡ N)

The time complexity is O(N log N) due to sorting the meetings, and the space complexity is O(log N) because of the recursive stack used during the merge process.

What Interviewers Usually Probe

Can the candidate explain how sorting affects the merging process?
How well does the candidate handle large input sizes efficiently?
Is the candidate able to handle edge cases, such as no meetings or full-day meetings?

Common Pitfalls or Variants

Common pitfalls

Forgetting to merge overlapping meetings before counting the free days.
Incorrectly handling edge cases like no free days or all days being booked.
Misunderstanding the problem and incorrectly returning the days with meetings instead of without.

Follow-up variants

What if meetings are given in a random order?
How would the solution change if the input days were larger?
What if meetings don't overlap at all?

FAQ

How does sorting help solve the Count Days Without Meetings problem?

Sorting the meetings ensures that overlapping intervals are adjacent, which simplifies the merging process and reduces the number of operations needed.

What is the time complexity of the solution?

The time complexity is O(N log N) due to sorting the meetings, where N is the number of meetings.

What if no meetings are scheduled?

If no meetings are scheduled, all days are free, so the answer would be equal to the total number of days available for work.

How do you merge overlapping meetings?

By sorting the meetings and checking if the start of the current meeting is within the end of the previous meeting. If so, merge them by updating the end time of the previous meeting.

How can I optimize this problem for large inputs?

The solution can be optimized by sorting the meetings in O(N log N) time, and then iterating through them once to merge and count free days, which ensures efficient handling of large inputs.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        ans = last = 0
        for st, ed in meetings:
            if last < st:
                ans += st - last - 1
            last = max(last, ed)
        ans += days - last
        return ans

Continue Practicing

#3186 maximum total damage with spell casting #3194 minimum average of smallest and largest elements #3143 maximum points inside the square