Count Days Without Meetings

Medium

Asked by:

18 views

Topics:

ArraysGreedy Algorithms

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^thday.

Example 3:

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

Output: 0

Explanation:

Meetings are scheduled for all working days.

Constraints:

1 <= days <= 10⁹
1 <= meetings.length <= 10⁵
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for each element in the input array? Are they integers? Could they be negative?
Could the input array be empty or null? If so, what should be the return value?
Is there a maximum number of meetings that can occur in a single day?
Are the meetings guaranteed to be non-overlapping? If overlapping meetings are possible, how should they be handled?
Can you provide an example input and the corresponding expected output to clarify the problem further?

Brute Force Solution

Approach

The brute force approach is like manually checking every single day on a calendar. We want to find days where there are no meetings. We'll examine each day one by one to see if it has a meeting or not.

Here's how the algorithm would work step-by-step:

Start with the very first day in the range of days we care about.
Check if there is a meeting scheduled for that day.
If there is no meeting on that day, mark it as a 'free' day.
Move on to the next day and repeat the process of checking for meetings.
Continue this process for every single day until you have checked all the days in the range.
Finally, count the total number of 'free' days you marked. That number is the answer.

Code Implementation

def count_days_without_meetings_brute_force(start_date, end_date, meetings):
    number_of_free_days = 0

    # Iterate through each day in the given range
    for current_date in range(start_date, end_date + 1):

        has_meeting_today = False

        # Check if there's a meeting on the current day
        for meeting_date in meetings:
            if current_date == meeting_date:
                has_meeting_today = True

                break

        # If no meeting, increment the free days count
        if not has_meeting_today:
            number_of_free_days += 1

    return number_of_free_days

Big(O) Analysis

Time Complexity

O(n*m) – Let 'n' be the total number of days in the range we are considering and 'm' be the number of meetings scheduled. For each of the 'n' days, we iterate through all 'm' meetings to check for overlaps. This leads to 'n' iterations, where each iteration involves checking 'm' meetings. Therefore, the total number of operations is proportional to n * m, giving us a time complexity of O(n*m).

Space Complexity

O(1) – The provided explanation details a brute-force approach that iterates through each day to check for meetings. It doesn't explicitly mention any auxiliary data structures being created to store information about days or meetings beyond single day being checked. The algorithm seems to only use a counter for free days, which uses constant space. Therefore, the space complexity is constant, independent of the number of days, which we can consider as the input size N. The auxiliary space is O(1).

Optimal Solution

Approach

The problem asks us to find how many days we don't have meetings, given a set of meeting schedules that span across several days. The most efficient approach is to focus on identifying continuous free time blocks, and then add up their lengths.

Here's how the algorithm would work step-by-step:

Create a master list of all days based on the start and end dates of all meetings.
Mark each day as 'busy' if it has a meeting scheduled on that day.
Find stretches of consecutive 'free' days (days that aren't marked as 'busy').
For each free stretch, count how many days it contains.
Add up the lengths of all the free stretches. The total is the number of days without meetings.

Code Implementation

def count_days_without_meetings(meetings):
    all_days = set()
    for start_date, end_date in meetings:
        for day in range(start_date, end_date + 1):
            all_days.add(day)

    busy_days = set()
    for start_date, end_date in meetings:
        for day in range(start_date, end_date + 1):
            busy_days.add(day)

    free_days_count = 0
    current_free_streak = 0
    sorted_days = sorted(list(all_days))

    # Iterate sorted days to calculate total free days
    for day in sorted_days:
        if day not in busy_days:
            current_free_streak += 1
        else:
            free_days_count += current_free_streak
            current_free_streak = 0

    free_days_count += current_free_streak

    # This is the final total number of days without meetings
    return free_days_count

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operations in this approach involve initially creating a master list of days and marking days as busy based on meeting schedules. Assuming 'n' represents the number of meetings and the range of dates spanned, sorting the meetings to create the master list typically takes O(n log n) time. The process of marking each day as busy iterates through the meetings and the range of days, contributing O(n) to the time complexity at most. Finding stretches of free days is linear with the size of the master list (which is at most O(n)), so it has O(n) complexity. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The space complexity is determined by the 'master list of all days' created in step 1, which is based on the start and end dates of all meetings. In the worst case, all meetings span distinct days, resulting in a list proportional to the number of days covered by all the meeting schedules, where N represents the total number of days covered. The algorithm also marks each day as 'busy' which will require, at worst, storing a boolean value for each of the N days. Therefore, the auxiliary space used scales linearly with N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
meetings array is null or empty	Return 0, as there are no meetings scheduled, so all days are free.
startDay is after endDay	Return 0, as this represents an invalid date range.
meetings array contains null meeting objects	Ignore the null meeting objects and continue processing valid meetings.
meetings array contains meeting objects where start or end time is outside the startDay and endDay range	Clip the meeting to the startDay and endDay to ensure that we only count meeting days within the range.
startDay and endDay are the same day	Check if any meeting overlaps this single day, return 0 if it overlaps and 1 if it does not.
Integer overflow if calculating the number of days between startDay and endDay	Use long integer type for days calculation to avoid overflow.
Meetings that span multiple days	Iterate from the meeting's start day to its end day and mark each day as a meeting day.
Meetings that completely overlap	Union the overlapped meeting days into a single time range to avoid double-counting.

meetings array is null or empty

How to Handle:

Return 0, as there are no meetings scheduled, so all days are free.

startDay is after endDay

How to Handle:

Return 0, as this represents an invalid date range.

meetings array contains null meeting objects

How to Handle:

Ignore the null meeting objects and continue processing valid meetings.

meetings array contains meeting objects where start or end time is outside the startDay and endDay range

How to Handle:

Clip the meeting to the startDay and endDay to ensure that we only count meeting days within the range.

startDay and endDay are the same day

How to Handle:

Check if any meeting overlaps this single day, return 0 if it overlaps and 1 if it does not.

Integer overflow if calculating the number of days between startDay and endDay

How to Handle:

Use long integer type for days calculation to avoid overflow.

Meetings that span multiple days

How to Handle:

Iterate from the meeting's start day to its end day and mark each day as a meeting day.

Meetings that completely overlap

How to Handle:

Union the overlapped meeting days into a single time range to avoid double-counting.