Problem Informations

• Problem Index: 3169
• Problem Link: Count Days Without Meetings
• Topics: Array, Sorting

Problem Description

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^th day.

Example 3:

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

Output: 0

Explanation:

Meetings are scheduled for all working days.

Constraints:

• $1 \leq days \leq 10^9$
• $1 \leq meetings.length \leq 10^5$
• $meetings[i].length == 2$
• $1 \leq meetings[i][0] \leq meetings[i][1] \leq days$

Intuition

The problem involves finding the number of days an employee is available for work without any meetings scheduled. Given the overlap of meetings, the idea is to identify the gaps or free days between these scheduled meetings. By sorting and sequentially analyzing the meetings, we can efficiently track these gaps and thus determine the required count of free days.

Approach

The approach can be broken down into several key steps:

1. Initialization: We begin by setting up two crucial variables: availableDays (to count the number of days the employee is free) and lastEndDay (to track the end of the last meeting that has been processed).

2. Sorting: The list of meetings is sorted based on their starting days. This ensures that we can process the meetings sequentially and straightforwardly identify gaps between them.

3. Dummy Meeting Addendum: A dummy meeting (totalDays + 1, totalDays + 1) is appended to the list of meetings. This simplifies the logic by ensuring that any gaps after the last real meeting are handled uniformly within the loop, avoiding separate post-loop logic.

4. Iteration and Calculation:

   • For each meeting, calculate the number of free days between the lastEndDay and the current meeting’s start day (meeting[0]). The formula meeting[0] - lastEndDay - 1 determines the number of days available between meetings. The max function ensures no negative values are added in case meetings overlap or are contiguous.
   • Update the lastEndDay to the maximum of its current value and the current meeting’s end day (meeting[1]). This keeps track of the furthest-reaching meeting end day encountered.

5. Return the Result: Once all meetings have been processed, availableDays holds the total count of days when the employee is free and not engaged in any meetings. This value is returned as the result.

The algorithm efficiently handles the constraints by using sorting (which is feasible given the constraints) and a single traversal of the meetings, leading to an overall complexity largely determined by the sorting step (O(n \log n)), where (n) is the number of meetings. This makes the solution scalable within the provided limits.

Code

C++

class Solution {
public:
    int countDays(int totalDays, vector<vector<int>>& meetings) {
        // Variable to store the count of available days without meetings
        int availableDays = 0;
        
        // Variable to keep track of the last end day of meetings considered
        int lastEndDay = 0;
        
        // Sort meetings by their start day to ensure sequential processing
        sort(meetings.begin(), meetings.end());
        
        // Add a dummy meeting beyond the last day to simplify the logic
        meetings.push_back({totalDays + 1, totalDays + 1});
        
        // Iterate over each meeting
        for (vector<int>& meeting : meetings) {
            // Calculate and add up the free days between the last meeting and the current one
            availableDays += max(meeting[0] - lastEndDay - 1, 0);
            
            // Update the lastEndDay to the maximum end day encountered so far
            lastEndDay = max(lastEndDay, meeting[1]);
        }
        
        // Return the total count of free available days
        return availableDays;
    }
};

Python

class Solution:
    def countDays(self, totalDays, meetings):
        # Variable to store the count of available days without meetings
        availableDays = 0
        
        # Variable to keep track of the last end day of meetings considered
        lastEndDay = 0
        
        # Sort meetings by their start day to ensure sequential processing
        meetings.sort()
        
        # Add a dummy meeting beyond the last day to simplify the logic
        meetings.append([totalDays + 1, totalDays + 1])
        
        # Iterate over each meeting
        for meeting in meetings:
            # Calculate and add up the free days between the last meeting and the current one
            availableDays += max(meeting[0] - lastEndDay - 1, 0)
            
            # Update the lastEndDay to the maximum end day encountered so far
            lastEndDay = max(lastEndDay, meeting[1])
        
        # Return the total count of free available days
        return availableDays

Complexity

• Time complexity: $O(n \log n)$

  The time complexity is dominated by the sorting step, which is $O(n \log n)$, where $n$ is the number of meetings. Sorting the list of meetings by their start day is the most computationally expensive operation in the algorithm. Iterating over the meetings and calculating available days both run in linear time, $O(n)$. Therefore, the overall time complexity remains $O(n \log n)$.

• Space complexity: $O(1)$

  The space complexity is $O(1)$, as the algorithm uses a constant amount of additional space that does not depend on the input size. Variables like availableDays, lastEndDay, and some temporary storage do not scale with the size of the input. The use of a constant extra element in the meetings list, added at the end, still results in a space complexity of $O(1)$.