3169. Count Days Without Meetings

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.

Intuition

To solve this problem, we can think about using a sorting strategy. Each meeting can potentially create a gap where no meetings are scheduled if it doesn't overlap with previous meetings.

Sorting the Meetings: We start by sorting all the meetings based on their starting day. This helps us process the meetings in the chronological order of when they start.
Track the Last Meeting End: We maintain a variable last to keep track of the maximum day until which meetings have already been scheduled. Initially, this is set to 0.
Identify Gaps: As we iterate over each meeting, we check if there is a gap between last and the current meeting's start day:
- If last < start_i, there’s a clear gap of days where no meetings are scheduled. We calculate the number of these days and add them to our answer.
- Otherwise, the meetings either overlap or are contiguous.
Expand the Meeting Scope: After checking for gaps, we update last to the maximum of its current value and the current meeting's end day. This ensures we're always considering the farthest day up to which meetings are scheduled.
Check Remaining Days: After processing all meetings, if last < days, there are still some days after the last meeting where the employee can work without meetings. Add these days to the answer.

By following these steps, we can efficiently calculate the number of available days without scheduled meetings.

Learn more about Sorting patterns.

Solution Approach

The solution follows a structured approach to identify the days available for work without any scheduled meetings by leveraging sorting and iteration.

Sort Meetings: We begin by sorting the meetings array based on the start day of each meeting. This sorting allows us to process each meeting in the order they begin, which is critical for identifying gaps between meetings.
```
meetings.sort()
```
Initialize Variables: We define two variables: ans to count available workdays and last to track the furthest day any meeting has ended.
```
ans = last = 0
```
Iterate Through Meetings: We loop through each meeting represented as (st, ed), which stands for start and end days:
- Check for Gaps: If the current last day is less than the start day of the current meeting (st), it indicates a gap period. The number of such available days is st - last - 1. We add this value to ans.
```
if last < st:
    ans += st - last - 1
```
- Update Last Day: For each meeting, update the last day to the maximum of the current last and the end day of the meeting (ed). This ensures that last always holds the furthest day up to which meetings are scheduled.
```
last = max(last, ed)
```
Check the Remaining Available Days: After processing all meetings, if last is less than the total number of days (days), it means there are some remaining days after the last meeting that are available for work. Add these days to ans.
```
ans += days - last
```
Return the Result: Finally, the ans variable, which accumulates all the available workdays not covered by meetings, is returned.
```
return ans
```

By following this algorithm, we efficiently determine the total number of days the employee can work without any scheduled meetings, taking into account overlapping and contiguous meetings.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example to illustrate the solution approach:

Suppose days is 10, representing the employee's availability from day 1 to day 10. The meetings represented by the meetings array are [[1, 2], [5, 6], [8, 8]]. Each sub-array [start_i, end_i] indicates the start and end days of a particular meeting.

Steps:

Sort the Meetings: The meetings are already sorted in this example: [[1, 2], [5, 6], [8, 8]].
Initialize Variables:
- ans = 0: This will hold the count of available days.
- last = 0: Represents the last day up to which meetings are scheduled.
Iterate Through Meetings:
- First Meeting [1, 2]:
  - Since last < start (0 < 1), there's a gap from day 1, but it's only 1 day before the meeting starts. ans += (1 - 0 - 1) = 0.
  - Update last = 2.
- Second Meeting [5, 6]:
  - last < start (2 < 5), so there's a gap from day 3 to day 4, which is 2 days. ans += (5 - 2 - 1) = 2.
  - Update last = 6.
- Third Meeting [8, 8]:
  - last < start (6 < 8), there's a gap on day 7. ans += (8 - 6 - 1) = 1.
  - Update last = 8.
Check Remaining Days:
- Since last < days (8 < 10), there are remaining days available for work—days 9 and 10. So, ans += (10 - 8) = 2.
Return the Result:
- The total number of available workdays with no meetings is ans = 2 + 1 + 2 = 5.

The employee has 5 days without any scheduled meetings, specifically on days 3, 4, 7, 9, and 10.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countDays(self, days: int, meetings: List[List[int]]) -> int:
5        # Sort the meetings by their starting day
6        meetings.sort()
7
8        # Initialize the answer to count free days and 'last' to track the last meeting's end day
9        free_days_count = 0
10        last_meeting_end = 0
11
12        # Iterate through each meeting
13        for start_day, end_day in meetings:
14            # If the last meeting ends before the current meeting starts,
15            # increment free_days_count by the days between them
16            if last_meeting_end < start_day:
17                free_days_count += start_day - last_meeting_end - 1
18
19            # Update the last meeting end day to the maximum of the current end day or last_meeting_end
20            last_meeting_end = max(last_meeting_end, end_day)
21
22        # Add the days after the last meeting ends to the total free days
23        free_days_count += days - last_meeting_end
24
25        return free_days_count
26

1import java.util.Arrays;
2
3class Solution {
4    public int countDays(int days, int[][] meetings) {
5        // Sort the meetings based on their starting day
6        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
7      
8        int ans = 0; // To hold the count of free days
9        int last = 0; // To track the last day covered by meetings
10
11        // Iterate over all the meetings
12        for (int[] meeting : meetings) {
13            int start = meeting[0];
14            int end = meeting[1];
15          
16            // If there are free days before the start of this meeting
17            if (last < start) {
18                ans += start - last - 1; // Count these free days
19            }
20          
21            // Update the last covered day
22            last = Math.max(last, end);
23        }
24      
25        // Add any remaining days after the last meeting to the free days
26        ans += days - last;
27
28        return ans; // Return the total count of free days
29    }
30}
31

1class Solution {
2public:
3    int countDays(int days, vector<vector<int>>& meetings) {
4        // Sort meetings by start time, and if equal, by end time
5        sort(meetings.begin(), meetings.end());
6      
7        int ans = 0; // To store the number of free days
8        int last = 0; // Track the last day up to which meetings are scheduled
9      
10        // Iterate through each meeting
11        for (auto& meeting : meetings) {
12            int start = meeting[0]; // Start day of current meeting
13            int end = meeting[1];   // End day of current meeting
14          
15            // If there's a gap between the last meeting day and current start
16            if (last < start) {
17                // Add the number of free days between last day and current start
18                ans += start - last - 1;
19            }
20          
21            // Update the last day to the maximum of current last or end of current meeting
22            last = max(last, end);
23        }
24      
25        // Include any remaining days after the last meeting
26        ans += days - last;
27      
28        return ans; // Return total number of free days
29    }
30};
31

1// Function to count the number of days with no scheduled meetings
2function countDays(days: number, meetings: number[][]): number {
3    // Sort meetings based on their start times in ascending order
4    meetings.sort((a, b) => a[0] - b[0]);
5
6    // Initialize the count of free days (ans) and the last occupied day (last)
7    let ans = 0;
8    let last = 0;
9
10    // Iterate over each meeting
11    for (const [start, end] of meetings) {
12        // If there's a gap between the last occupied day and the current meeting's start day
13        if (last < start) {
14            // Add those free days to the answer
15            ans += start - last - 1;
16        }
17        // Update 'last' to the farthest day occupied by meetings
18        last = Math.max(last, end);
19    }
20  
21    // Add the free days after the last meeting until the total number of days
22    ans += days - last;
23
24    // Return the total count of free days
25    return ans;
26}
27

Time and Space Complexity

The time complexity of the code is O(n * log n) because it involves sorting the meetings list, which contains n intervals, and then iterating through the sorted list which takes O(n) time.

The space complexity is O(log n) due to the space requirements of the sorting algorithm, which typically uses O(log n) extra space for the recursion stack.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know