Count Days Without Meetings — Medium Problem & Solution

Problem statement

An employee is available for work on days 1 through days. meetings[i] = [start, end] is a meeting spanning those days inclusive; meetings may overlap.

Return the number of days with no meeting scheduled.

Example 1

Input: days = 10, meetings = [[5,7],[1,3],[9,10]]
Output: 2
Explanation: Days 4 and 8 are free.

Example 2

Input: days = 5, meetings = [[2,4],[1,3]]
Output: 1
Explanation: The two meetings cover days 1 to 4.

Example 3

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

Constraints

• 1 <= days <= 10^9
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

How to solve Count Days Without Meetings

Sort the meetings by start and sweep, keeping reach — the furthest day covered so far. Each meeting adds only the part beyond reach, so the total covered count is exact even with overlaps.

Approach

1. Sort the meetings by start day.
2. For each, start counting from max(start, reach + 1).
3. If that is at most the meeting's end, add the span and advance reach.
4. Return days - covered.

Why it works

Clamping each meeting's start to reach + 1 is what makes overlapping and fully-nested meetings harmless — the overlap is simply not counted twice, and a meeting entirely inside an earlier one contributes nothing. Working with counts rather than a day-by-day array is what keeps this feasible at days = 10^9.

Complexity

• Time — O(m log m)
• Space — O(m)

Pitfalls

• Marking each day individually is impossible at 10^9.
• A meeting contained in an earlier one must add zero, not its full length.
• Both endpoints are inclusive, so a meeting [x, x] covers one day.

Reference solution

Python

from typing import List

def countDays(days: int, meetings: List[List[int]]) -> int:
    covered = 0
    reach = 0
    for start, end in sorted(meetings):
        s = max(start, reach + 1)
        if end >= s:
            covered += end - s + 1
            reach = end
    return days - covered

JavaScript

var countDays = function(days, meetings) {
    var sorted = meetings.slice();
    sorted.sort(function(a, b) { return a[0] - b[0]; });
    var covered = 0, reach = 0;
    for (var i = 0; i < sorted.length; i++) {
        var s = sorted[i][0] > reach + 1 ? sorted[i][0] : reach + 1;
        if (sorted[i][1] >= s) {
            covered += sorted[i][1] - s + 1;
            reach = sorted[i][1];
        }
    }
    return days - covered;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium