Problem Description

You have an employee who is available to work for a certain number of days (from day 1 to day days). You're also given a list of meetings where each meeting is represented as [start_i, end_i], indicating the meeting runs from day start_i to day end_i (both days inclusive).

Your task is to find out how many days the employee is free to work when there are no meetings scheduled.

Key points to understand:

• The employee is available from day 1 to day days
• Each meeting occupies a range of days (inclusive of both start and end days)
• Meetings can overlap with each other (multiple meetings can happen on the same days)
• You need to count the total number of days where NO meetings are scheduled

For example, if days = 10 and meetings = [[5,7], [1,3], [9,10]]:

• Days 1-3 have meetings
• Day 4 is free
• Days 5-7 have meetings
• Day 8 is free
• Days 9-10 have meetings
• So the answer would be 2 (days 4 and 8 are free)

The solution approach sorts the meetings by start time and merges overlapping intervals to find the gaps where no meetings occur. It keeps track of the last covered day and counts the gaps between consecutive meeting periods, plus any remaining days after the last meeting ends.

Intuition

Think about this problem visually - imagine a timeline from day 1 to days. Each meeting blocks out a portion of this timeline. Our goal is to find the gaps where no meetings exist.

The key insight is that we need to handle overlapping meetings. If we have meetings [2,5] and [4,7], they overlap and together block days 2-7. Simply counting each meeting's duration separately would incorrectly count days 4-5 twice.

To efficiently find the free days, we can process meetings in chronological order. By sorting meetings by their start time, we can walk through the timeline from left to right, keeping track of the "furthest day covered so far" by any meeting.

As we process each meeting:

• If there's a gap between the last covered day and the current meeting's start, those gap days are free days
• We then extend our coverage to include the current meeting, but only if it extends beyond what we've already covered (handling overlaps)

For example, with sorted meetings [1,3], [5,7], [6,8]:

• After [1,3], we've covered up to day 3
• Before [5,7] starts, day 4 is free (gap from 3 to 5)
• After [5,7], we've covered up to day 7
• Meeting [6,8] starts at 6 (already covered), but extends our coverage to day 8

This approach naturally handles overlapping meetings because we always track the maximum end day seen so far. By maintaining this "last covered day" variable and checking for gaps before each new meeting, we can count all free days in a single pass through the sorted meetings.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a sorting and merging strategy to find the free days:

Step 1: Sort the meetings

meetings.sort()

We sort all meetings by their start time. This allows us to process them chronologically and identify gaps between consecutive meeting periods.

Step 2: Initialize tracking variables

ans = last = 0

• ans: Accumulates the count of free days
• last: Tracks the latest end day covered by meetings processed so far

Step 3: Process each meeting to find gaps

for st, ed in meetings:
    if last < st:
        ans += st - last - 1
    last = max(last, ed)

For each meeting [st, ed]:

• Check for gap: If last < st, there's a gap between the last covered day and this meeting's start
  • The number of free days in this gap is st - last - 1
  • For example, if last = 3 and st = 6, days 4 and 5 are free (6 - 3 - 1 = 2 days)
• Update coverage: Set last = max(last, ed) to extend our coverage
  • We use max to handle overlapping meetings correctly
  • If the current meeting ends before last, we keep last unchanged

Step 4: Account for remaining days

ans += days - last

After processing all meetings, if last < days, there are free days from last + 1 to days. We add these remaining free days to our answer.

Example walkthrough with days = 10 and meetings = [[5,7], [1,3], [9,10]]:

1. After sorting: [[1,3], [5,7], [9,10]]
2. Initialize: ans = 0, last = 0
3. Process [1,3]: Gap from 0 to 1 gives 0 free days, last = 3
4. Process [5,7]: Gap from 3 to 5 gives 1 free day (day 4), last = 7
5. Process [9,10]: Gap from 7 to 9 gives 1 free day (day 8), last = 10
6. Add remaining: 10 - 10 = 0 days
7. Total: ans = 2

The time complexity is O(n log n) for sorting, and space complexity is O(1) excluding the input.

Example Walkthrough

Let's walk through a concrete example with days = 12 and meetings = [[2,4], [6,8], [3,5], [10,11]].

Step 1: Sort meetings by start time

• Original: [[2,4], [6,8], [3,5], [10,11]]
• After sorting: [[2,4], [3,5], [6,8], [10,11]]

Step 2: Initialize variables

• ans = 0 (count of free days)
• last = 0 (last covered day)

Step 3: Process each meeting

Meeting [2,4]:

• Check gap: last = 0 < st = 2, so there's a gap
• Free days in gap: 2 - 0 - 1 = 1 (day 1 is free)
• Update ans = 0 + 1 = 1
• Update last = max(0, 4) = 4

Meeting [3,5]:

• Check gap: last = 4 < st = 3? No, 4 ≥ 3, so no gap
• No free days to add
• Update last = max(4, 5) = 5 (extends coverage by 1 day)

Meeting [6,8]:

• Check gap: last = 5 < st = 6, so there's a gap
• Free days in gap: 6 - 5 - 1 = 0 (no days between 5 and 6)
• Update ans = 1 + 0 = 1
• Update last = max(5, 8) = 8

Meeting [10,11]:

• Check gap: last = 8 < st = 10, so there's a gap
• Free days in gap: 10 - 8 - 1 = 1 (day 9 is free)
• Update ans = 1 + 1 = 2
• Update last = max(8, 11) = 11

Step 4: Add remaining days

• Remaining days: days - last = 12 - 11 = 1 (day 12 is free)
• Final answer: ans = 2 + 1 = 3

Verification:

• Day 1: Free ✓
• Days 2-5: Covered by meetings [2,4] and [3,5]
• Days 6-8: Covered by meeting [6,8]
• Day 9: Free ✓
• Days 10-11: Covered by meeting [10,11]
• Day 12: Free ✓

Total free days = 3, which matches our calculated answer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n), where n is the number of meetings.

The dominant operation in this algorithm is the sorting of the meetings list using meetings.sort(), which has a time complexity of O(n × log n) for Python's Timsort algorithm. After sorting, the code iterates through the meetings list once with a for loop, performing constant-time operations in each iteration, contributing O(n) to the overall complexity. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(log n), where n is the number of meetings.

The space complexity is determined by the sorting algorithm. Python's sort() method uses Timsort, which requires O(log n) space in the worst case for its recursion stack when performing the merge operations. The algorithm itself only uses a constant amount of extra space for variables (ans, last, st, ed), which is O(1). Therefore, the overall space complexity is O(log n).

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

Common Pitfalls

1. Incorrectly Calculating Gap Days

The Pitfall: When calculating the free days between the last covered day and the current meeting's start, it's easy to make an off-by-one error. A common mistake is using start_day - last_covered_day instead of start_day - last_covered_day - 1.

Why This Happens: The confusion arises because meetings include both start and end days. If last_covered_day = 3 and the next meeting starts at start_day = 6, the free days are 4 and 5 (not 3 days but 2 days).

Incorrect Code:

if last_covered_day < start_day:
    free_days += start_day - last_covered_day  # Wrong! This counts day 6 as free

Correct Solution:

if last_covered_day < start_day:
    free_days += start_day - last_covered_day - 1  # Correct: counts days 4 and 5

2. Not Handling Overlapping Meetings Properly

The Pitfall: Simply updating last_covered_day = end_day without using max() can lead to incorrect results when meetings overlap or when a shorter meeting is contained within a longer one.

Example Scenario:

• Meetings: [[1,5], [2,3]] after sorting
• Processing [1,5]: last_covered_day = 5
• Processing [2,3]: If we set last_covered_day = 3 (wrong!), we'd incorrectly think days 4-5 are now uncovered

Incorrect Code:

for start_day, end_day in meetings:
    if last_covered_day < start_day:
        free_days += start_day - last_covered_day - 1
    last_covered_day = end_day  # Wrong! Can move backwards

Correct Solution:

for start_day, end_day in meetings:
    if last_covered_day < start_day:
        free_days += start_day - last_covered_day - 1
    last_covered_day = max(last_covered_day, end_day)  # Correct: never move backwards

3. Forgetting to Count Days After the Last Meeting

The Pitfall: Only counting gaps between meetings and forgetting to add the free days after all meetings end.

Example: If days = 10 and the last meeting ends on day 7, days 8, 9, and 10 are free but won't be counted without the final step.

Incorrect Code:

def countDays(self, days: int, meetings: List[List[int]]) -> int:
    meetings.sort()
    free_days = 0
    last_covered_day = 0
  
    for start_day, end_day in meetings:
        if last_covered_day < start_day:
            free_days += start_day - last_covered_day - 1
        last_covered_day = max(last_covered_day, end_day)
  
    return free_days  # Missing the remaining days!

Correct Solution:

def countDays(self, days: int, meetings: List[List[int]]) -> int:
    meetings.sort()
    free_days = 0
    last_covered_day = 0
  
    for start_day, end_day in meetings:
        if last_covered_day < start_day:
            free_days += start_day - last_covered_day - 1
        last_covered_day = max(last_covered_day, end_day)
  
    # Don't forget to add remaining days after the last meeting
    free_days += days - last_covered_day
  
    return free_days

4. Edge Case: Empty Meetings List

The Pitfall: Not considering what happens when the meetings list is empty. The algorithm should return days as all days are free.

Why It Works: The current solution handles this correctly because:

• If meetings is empty, the loop doesn't execute
• last_covered_day remains 0
• The final line adds days - 0 = days to free_days

However, being aware of this edge case helps ensure the solution is robust.