LeetCode Solutions Blog

Count Days Without Meetings

Number: 3430

Difficulty: Medium

Paid? No

Problem Description

Given a total number of days and a list of meeting intervals (which may overlap), determine how many days are free (i.e. days where no meeting is scheduled).

Key Insights

Because meetings may overlap, merge overlapping intervals to avoid counting the same day more than once.
Instead of tracking each individual day (which is not feasible for days up to 10^9), calculate the total days covered by the merged intervals.
Sort the intervals by start day to simplify the merging process.
Subtract the total days occupied by meetings from the total available days.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the meeting intervals. Space Complexity: O(n) for storing the merged intervals.

Solution

The solution involves first sorting the meetings by their start day. Then, iterate through the sorted intervals to merge overlapping or contiguous meeting intervals. Once all intervals are merged, compute the number of days covered by these intervals. Finally, subtract the covered days from the total days to get the number of free days. This approach ensures that we efficiently handle large input sizes without iterating over every day.

Code Solutions

# Python solution for Count Days Without Meetings
def count_free_days(days, meetings):
    # Sort meetings based on the start day
    meetings.sort(key=lambda x: x[0])
    
    # List to hold merged meeting intervals
    merged = []
    
    for meeting in meetings:
        # If merged is empty or current meeting does not overlap with the last merged meeting
        if not merged or meeting[0] > merged[-1][1]:
            merged.append(meeting)
        else:
            # Merge the meeting by extending the end if needed
            merged[-1][1] = max(merged[-1][1], meeting[1])
    
    # Calculate total days covered by meetings
    total_meeting_days = 0
    for interval in merged:
        # interval[1] - interval[0] + 1 gives the length of the interval
        total_meeting_days += (interval[1] - interval[0] + 1)
    
    # Free days are days minus total meeting days
    return days - total_meeting_days

# Example usage:
print(count_free_days(10, [[5,7],[1,3],[9,10]]))  # Expected output: 2