LeetCode 3169 - Count Days Without Meetings

The problem gives us a total number of working days, numbered from 1 to days, along with a list of meeting intervals. Each interval [start, end] represents a meeting that occupies every day from start through end, inclusive.

leetcodemediumarraysorting

LeetCode Problem 3169

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

LeetCode 3169 - Count Days Without Meetings

Problem Understanding

The problem gives us a total number of working days, numbered from 1 to days, along with a list of meeting intervals. Each interval [start, end] represents a meeting that occupies every day from start through end, inclusive.

Our task is to determine how many days remain completely free, meaning no meeting covers those days.

A key detail is that meetings may overlap. For example, if one meeting covers days 2 through 5 and another covers days 4 through 7, then days 4 and 5 are shared between the two meetings. We must avoid double-counting these overlapping days when determining how many total days are occupied.

The input constraints are important:

  • days can be as large as 10^9
  • The number of meetings can be up to 10^5

The extremely large value of days immediately tells us that iterating through every day individually is not feasible. Even storing an array of size 10^9 would be impossible within memory limits.

The number of meeting intervals, however, is manageable at 10^5, which suggests that the correct solution should work primarily with intervals rather than individual days.

Several edge cases are important:

  • Meetings may completely overlap each other.
  • Meetings may partially overlap.
  • Meetings may touch directly, such as [1,3] and [4,5], which together cover a continuous range without gaps.
  • A single meeting may already cover all days.
  • Meetings may appear in arbitrary order, so sorting is necessary.
  • There may be only one meeting interval.

The core challenge is therefore an interval merging problem. We need to compute the total number of distinct occupied days, then subtract that value from the total number of days.

Approaches

Brute Force Approach

A straightforward solution would be to mark every day that contains a meeting.

We could create a boolean array of size days + 1, where each position represents whether that day is occupied. Then, for every meeting interval [start, end], we iterate through all days in that range and mark them as occupied.

After processing all meetings, we count how many days remain unmarked.

This approach is correct because every meeting day is explicitly recorded, and overlapping meetings naturally collapse into the same marked positions.

However, this approach is far too slow and memory-intensive for the given constraints.

If days = 10^9, we cannot allocate an array with one billion entries. Additionally, iterating through every covered day could require billions of operations.

Optimal Approach

The key observation is that we do not care about individual days directly. Instead, we only care about the union of all meeting intervals.

If we sort meetings by starting day, we can merge overlapping or adjacent intervals into larger continuous blocks.

For example:

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

becomes:

[1,5], [7,8]

Now we only need to compute the total length of these merged intervals.

The number of free days is:

days - occupied_days

This works efficiently because sorting takes O(n log n) time, and merging requires only a single linear scan afterward.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(days + total_interval_length) O(days) Marks every individual day
Optimal O(n log n) O(1) or O(n) depending on sorting implementation Merges overlapping intervals

Algorithm Walkthrough

  1. Sort the meetings by their starting day.

Sorting ensures that overlapping intervals appear next to each other. This makes merging possible with a single pass. 2. Initialize variables to track the current merged interval.

We keep:

  • current_start
  • current_end

These represent the interval currently being merged. 3. Start with the first meeting interval.

Since the meetings are sorted, the first interval becomes the initial merged interval. 4. Iterate through the remaining meetings.

For each interval [start, end], compare it with the current merged interval. 5. Check whether the intervals overlap or touch.

If:

start <= current_end + 1

then the intervals are continuous and should be merged.

Update:

current_end = max(current_end, end)
  1. Handle non-overlapping intervals.

If the current interval does not overlap, then the previous merged interval is complete.

Add its length to the occupied count:

occupied += current_end - current_start + 1

Then start a new merged interval. 7. Add the final merged interval.

After the loop ends, the last interval has not yet been counted, so we add its length. 8. Compute free days.

The answer is:

days - occupied

Why it works

After sorting, every overlapping or adjacent interval appears consecutively. The algorithm maintains the invariant that current_start and current_end always describe the merged form of all intervals processed so far that belong to the same continuous block.

Whenever a gap appears, the previous merged interval is finalized and counted exactly once. Because every occupied day belongs to exactly one merged interval, the total occupied count is correct. Subtracting from days therefore gives the exact number of free days.

Python Solution

from typing import List

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        meetings.sort()

        occupied_days = 0

        current_start, current_end = meetings[0]

        for start, end in meetings[1:]:
            if start <= current_end + 1:
                current_end = max(current_end, end)
            else:
                occupied_days += current_end - current_start + 1
                current_start, current_end = start, end

        occupied_days += current_end - current_start + 1

        return days - occupied_days

The implementation begins by sorting the meetings array. Python sorts lists of lists lexicographically, so intervals are automatically sorted by start day and then by end day.

The variables current_start and current_end track the active merged interval.

As we iterate through the remaining intervals, we determine whether the new interval overlaps or touches the current merged interval. If it does, we extend the current interval. Otherwise, we finalize the current interval by adding its length to occupied_days.

At the end of the loop, the final merged interval still needs to be counted, so we add it separately.

Finally, we subtract the occupied days from the total number of days to obtain the answer.

Go Solution

package main

import "sort"

func countDays(days int, meetings [][]int) int {
	sort.Slice(meetings, func(i, j int) bool {
		if meetings[i][0] == meetings[j][0] {
			return meetings[i][1] < meetings[j][1]
		}
		return meetings[i][0] < meetings[j][0]
	})

	occupiedDays := 0

	currentStart := meetings[0][0]
	currentEnd := meetings[0][1]

	for i := 1; i < len(meetings); i++ {
		start := meetings[i][0]
		end := meetings[i][1]

		if start <= currentEnd+1 {
			if end > currentEnd {
				currentEnd = end
			}
		} else {
			occupiedDays += currentEnd - currentStart + 1
			currentStart = start
			currentEnd = end
		}
	}

	occupiedDays += currentEnd - currentStart + 1

	return days - occupiedDays
}

The Go solution follows the same logic as the Python implementation.

One Go-specific detail is the use of sort.Slice with a custom comparator to sort intervals by starting day.

Go slices are mutable, so sorting happens in place without additional memory allocation.

Integer overflow is not a concern because the maximum possible value is within the range of Go's int on LeetCode platforms.

Worked Examples

Example 1

Input:

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

Step 1: Sort meetings

Sorted Meetings
[1,3]
[5,7]
[9,10]

Step 2: Initialize

Variable Value
current_start 1
current_end 3
occupied_days 0

Step 3: Process [5,7]

Since:

5 > 3 + 1

there is a gap.

Finalize [1,3]:

occupied_days += 3

Now:

Variable Value
occupied_days 3
current_start 5
current_end 7

Step 4: Process [9,10]

Since:

9 > 7 + 1

another gap exists.

Finalize [5,7]:

occupied_days += 3

Now:

Variable Value
occupied_days 6
current_start 9
current_end 10

Step 5: Finalize last interval

Length of [9,10]:

2

Total occupied:

8

Free days:

10 - 8 = 2

Answer:

2

Example 2

Input:

days = 5
meetings = [[2,4],[1,3]]

Step 1: Sort meetings

[1,3], [2,4]

Step 2: Merge

Since:

2 <= 3 + 1

the intervals overlap.

Merged interval becomes:

[1,4]

Occupied days:

4

Free days:

5 - 4 = 1

Answer:

1

Example 3

Input:

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

Only one interval exists.

Occupied days:

6

Free days:

6 - 6 = 0

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) extra space, excluding sorting Only a few variables are used

The sorting step is the most expensive part of the algorithm and requires O(n log n) time. After sorting, we perform a single linear pass through the meetings array.

The merging process itself uses only constant extra memory because we maintain only a few tracking variables.

Test Cases

from typing import List

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        meetings.sort()

        occupied_days = 0

        current_start, current_end = meetings[0]

        for start, end in meetings[1:]:
            if start <= current_end + 1:
                current_end = max(current_end, end)
            else:
                occupied_days += current_end - current_start + 1
                current_start, current_end = start, end

        occupied_days += current_end - current_start + 1

        return days - occupied_days

sol = Solution()

assert sol.countDays(10, [[5,7],[1,3],[9,10]]) == 2  # basic separated meetings
assert sol.countDays(5, [[2,4],[1,3]]) == 1  # overlapping intervals
assert sol.countDays(6, [[1,6]]) == 0  # all days occupied
assert sol.countDays(8, [[1,2],[3,4]]) == 4  # touching intervals merge
assert sol.countDays(20, [[1,5],[2,3],[4,10]]) == 10  # nested overlaps
assert sol.countDays(15, [[5,5]]) == 14  # single-day meeting
assert sol.countDays(7, [[2,2],[4,4],[6,6]]) == 4  # multiple isolated days
assert sol.countDays(100, [[1,100]]) == 0  # entire range occupied
assert sol.countDays(12, [[3,5],[7,9]]) == 6  # two separate meeting blocks
assert sol.countDays(9, [[1,2],[2,3],[3,4]]) == 5  # chain overlap
Test Why
[[5,7],[1,3],[9,10]] Validates separated intervals
[[2,4],[1,3]] Validates overlap merging
[[1,6]] Validates fully occupied range
[[1,2],[3,4]] Validates adjacent interval merging
[[1,5],[2,3],[4,10]] Validates nested overlaps
[[5,5]] Validates single-day meetings
[[2,2],[4,4],[6,6]] Validates isolated occupied days
[[1,100]] Validates maximum coverage
[[3,5],[7,9]] Validates multiple gaps
[[1,2],[2,3],[3,4]] Validates chain merging

Edge Cases

Completely Overlapping Meetings

An important edge case occurs when one meeting is fully contained within another, such as:

[1,10], [3,5], [6,8]

A buggy implementation might double-count overlapping portions. The merging process prevents this by extending intervals only when necessary and counting each merged interval exactly once.

Adjacent Intervals

Meetings like:

[1,3], [4,5]

do not technically overlap, but together they occupy a continuous sequence of days with no free gap between them.

The condition:

start <= current_end + 1

correctly merges these intervals so no false free day is introduced.

Single Meeting Covering Entire Range

If the input is:

days = 100
meetings = [[1,100]]

then every day is occupied.

Some implementations incorrectly leave uncounted days at the boundaries. This solution explicitly computes the full interval length using:

end - start + 1

which correctly includes both endpoints.