Count Days Without Meetings

Problem

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.

Examples

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 <= 10^9
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

Solution

Method 1 - Using the set

We can

• Use a set (or boolean array) to track days that are occupied by meetings.
• Traverse through the list of meetings, and mark all days within each meeting's range (start_i to end_i) as occupied in the tracking set/array.
• Any day that is not marked as occupied after processing all meetings is considered a free day.

Steps

• Initialise a data structure (like a set or an array) to track which days are taken by meetings.
• Iterate through the meetings list, marking the occupied days.
• Finally, count the days between 1 and days that are not occupied.

This approach efficiently handles overlapping meetings because duplicates are eliminated in the set or overwritten in the boolean array. But will result in TLE for large days.

Code

Java

class Solution {
    public int countDays(int days, int[][] meetings) {
        // Create a HashSet to track occupied days
        HashSet<Integer> occupiedDays = new HashSet<>();

        // Mark all occupied days based on meetings
        for (int[] meeting : meetings) {
            for (int d = meeting[0]; d <= meeting[1]; d++) {
                occupiedDays.add(d);
            }
        }

        // Count the number of free days
        int ans = 0;
        for (int d = 1; d <= days; d++) {
            if (!occupiedDays.contains(d)) {
                ans++;
            }
        }

        return ans;
    }
}

Python

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        # Create a set to track occupied days
        occupied_days: set[int] = set()
        
        # Mark all occupied days based on meetings
        for meeting in meetings:
            for d in range(meeting[0], meeting[1] + 1):
                occupied_days.add(d)
        
        # Count the number of free days
        ans: int = 0
        for d in range(1, days + 1):
            if d not in occupied_days:
                ans += 1
        
        return ans

Complexity

• ⏰ Time complexity: O(n * m + days), where n is the number of meetings and m is the average range of meeting days.
  • For creating the list of occupied days: O(n * m)
  • Counting free days: O(days)
• 🧺 Space complexity: O(days)

Method 2 - Lazy marking using difference array

This method uses a Difference Array to efficiently mark ranges of occupied days without explicitly iterating over every day in each range. Instead of directly marking all days in a range as occupied, the approach works by marking the start and end points of ranges using a difference array. The occupancy status for all days is then computed using prefix sums over the difference array.

Steps

1. Difference Array Setup:
   • Create a difference array (difference[]) to represent changes at range boundaries:
     • Increment difference[start] by 1 to mark the start of a range.
     • Decrement difference[end + 1] by 1 to mark the end of a range.
   • This efficiently marks the ranges without manually iterating over all individual days within them.
2. Occupancy Array Construction:
   • Use a prefix sum across the difference array to construct the occupancy status of each day:
     • If the sum is positive at a day, it is occupied.
     • Otherwise, it is free.
3. Count Free Days:
   • Iterate over the occupancy array and count days that are not occupied.

Code

Java

class Solution {
    public int countDays(int days, int[][] meetings) {
        // Create a difference array to track ranges
        int[] difference = new int[days + 2];
        
        // Update difference array for ranges
        for (int[] meeting : meetings) {
            difference[meeting[0]]++;
            difference[meeting[1] + 1]--;
        }
        
        // Build the actual occupancy array from the difference array
        boolean[] occupied = new boolean[days + 1];
        int runningSum = 0;
        for (int d = 1; d <= days; d++) {
            runningSum += difference[d];
            occupied[d] = (runningSum > 0);  // If sum > 0, the day is occupied
        }
        
        // Count unoccupied days
        int ans = 0;
        for (int d = 1; d <= days; d++) {
            if (!occupied[d]) {
                ans++;
            }
        }
        
        return ans;
    }
}

Python

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        # Create a difference array to track ranges
        difference: List[int] = [0] * (days + 2)
        
        # Update difference array for ranges
        for meeting in meetings:
            difference[meeting[0]] += 1
            difference[meeting[1] + 1] -= 1
        
        # Build the actual occupancy array from the difference array
        occupied: List[bool] = [False] * (days + 1)
        running_sum: int = 0
        for d in range(1, days + 1):
            running_sum += difference[d]
            occupied[d] = (running_sum > 0)  # If sum > 0, the day is occupied
        
        # Count unoccupied days
        ans: int = 0
        for d in range(1, days + 1):
            if not occupied[d]:
                ans += 1
        
        return ans

Complexity

• ⏰ Time complexity: O(n + days), where n is the number of meetings.
  1. Updating difference array: O(n) → Loop through all n meetings.
  2. Constructing occupancy array: O(days) → Loop through all days.
  3. Counting free days: O(days) → Loop through all days.
• 🧺 Space complexity: O(days)
  1. Difference array: O(days).
  2. Occupancy array: O(days).

Dry Run

Suppose:

• days = 10
• meetings = [[1, 3], [5, 7]]

Execution:

1. Difference Array:

    [0, +1, 0, 0, -1, +1, 0, 0, -1, 0, 0]
   

2. Prefix Sum (occupancy status):

    [False, True, True, True, False, True, True, True, False, False, False]
   

3. Free Days:

   • Days {4, 8, 9, 10} are free.
   • Result: 4.

Method 3 - Using Sorting and Interval Merging

Instead of marking specific days, we can process the meetings as intervals, merge overlapping intervals, and calculate the total occupied range. Using this strategy, we minimise the computation to just the required number of intervals instead of days.

Steps

1. Sort Intervals:
   • Sort the meetings based on their start times. This helps us merge overlapping or adjacent intervals efficiently.
2. Merge Intervals:
   • Traverse the sorted intervals, merging overlapping ones into a single interval.
3. Count Occupied Days:
   • Calculate the total number of days occupied by these merged intervals.
4. Subtract from Total Days:
   • The total available days (days) minus the occupied days gives the count of free days.

Code

Java

class Solution {
    public int countDays(int days, int[][] meetings) {
        // Step 1: Sort meetings based on start time
        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));

        // Step 2: Merge overlapping intervals
        int mergedStart = meetings[0][0];
        int mergedEnd = meetings[0][1];
        long occupiedDays = 0; // Long to avoid integer overflow for large days

        for (int i = 1; i < meetings.length; i++) {
            int start = meetings[i][0];
            int end = meetings[i][1];

            if (start <= mergedEnd) {
                // Extend the current merged interval
                mergedEnd = Math.max(mergedEnd, end);
            } else {
                // Add the length of the previous merged interval
                occupiedDays += (mergedEnd - mergedStart + 1);
                // Start a new interval
                mergedStart = start;
                mergedEnd = end;
            }
        }

        // Add the last merged interval
        occupiedDays += (mergedEnd - mergedStart + 1);

        // Step 3: Calculate free days
        long freeDays = (long) days - occupiedDays; // Use long for very large days
        return (int) freeDays; // Cast result back to int
    }
}

Python

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        # Step 1: Sort meetings based on start time
        meetings.sort(key=lambda x: x[0])  # Sort by start time

        # Step 2: Merge overlapping intervals
        merged_start: int = meetings[0][0]
        merged_end: int = meetings[0][1]
        occupied_days: int = 0  # Keep track of total occupied days
        
        # Iterate through the sorted meetings
        for i in range(1, len(meetings)):
            start = meetings[i][0]
            end = meetings[i][1]

            if start <= merged_end:
                # Extend the current merged interval
                merged_end = max(merged_end, end)
            else:
                # Add the length of the previous merged interval
                occupied_days += (merged_end - merged_start + 1)
                # Start a new interval
                merged_start = start
                merged_end = end
        
        # Add the last merged interval
        occupied_days += (merged_end - merged_start + 1)
        
        # Step 3: Calculate free days
        free_days: int = days - occupied_days
        return free_days

Complexity

• ⏰ Time complexity: O(n log n), where n is the number of meetings.
  1. Sorting intervals: O(n log n) where n is the number of meetings.
  2. Merging intervals: O(n) since we iterate through the list of meetings.
• 🧺 Space complexity: O(1)  auxiliary space apart from the input.

Dry Run

Suppose:

• days = 10
• meetings = [[1, 3], [5, 7], [2, 6]]

Execution:

1. Sorted Meetings:

    [[1, 3], [2, 6], [5, 7]]
   

2. Merge Process:

   • First interval: [1, 3]
   • Extend to [1, 6] (merging [2, 6])
   • Extend to [1, 7] (merging [5, 7]).

3. Total Occupied Days:

   • Length of merged interval [1, 7] = 7 days.

4. Free Days:

    10 - 7 = 3
   

Result: 3 free days.