We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Days Without Meetings

Difficulty: Medium

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.

Key Insights

  • Each meeting occupies a range of days, and multiple meetings can overlap.
  • We need to determine the days that fall outside all scheduled meetings.
  • Sorting the meetings array can help in merging overlapping meetings and simplifying the count of available days.
  • The total number of days available for work is fixed, which allows for a straightforward calculation once the occupied days are known.

Space and Time Complexity

Time Complexity: O(n log n) - due to the sorting of the meetings array.
Space Complexity: O(n) - for storing the merged meetings.

Solution

To solve the problem, we can use the following steps:

  1. Sort the meetings based on their start day. This will help in merging overlapping meetings.
  2. Iterate through the sorted meetings to merge them into a single list of occupied days, ensuring that overlapping days are counted only once.
  3. Calculate the total number of available days by subtracting the number of occupied days from the total days.
  4. Return the count of available days.

The primary data structure used is a list to store the merged meetings, and the algorithmic approach involves sorting followed by a linear pass to merge intervals.

Code Solutions

def countDaysWithoutMeetings(days, meetings):
    # Sort meetings based on the start day
    meetings.sort()
    
    merged_meetings = []
    
    # Merge overlapping meetings
    for start, end in meetings:
        if not merged_meetings or merged_meetings[-1][1] < start:
            merged_meetings.append([start, end])
        else:
            merged_meetings[-1][1] = max(merged_meetings[-1][1], end)
    
    # Count the number of occupied days
    occupied_days = 0
    for start, end in merged_meetings:
        occupied_days += end - start + 1
    
    # Calculate the available days
    return days - occupied_days

# Example usage
print(countDaysWithoutMeetings(10, [[5,7],[1,3],[9,10]]))  # Output: 2
← Back to All Questions