Count Days Without Meetings

Medium
1002.

Count Days Without Meetings

Count Days Without Meetings is a medium coding problem on arrays and sorting, asked in Amazon, Google and Salesforce interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} days
 * @param {number[][]} meetings
 * @return {number}
 */
var countDays = function(days, meetings) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Days Without Meetings — Solution in Python, Java & C++

Count Days Without Meetings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Days Without Meetings is a medium coding problem on arrays and sorting, asked in Amazon, Google and Salesforce interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting
  • Asked at: Amazon, Google, Salesforce
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Count Days Without Meetings

  1. Hint 1

    days can be a billion, so the free days cannot be marked one by one.

  2. Hint 2

    Sort by start and sweep, tracking the furthest day covered so far.

  3. Hint 3

    Count covered days, then subtract from 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

Java

public static int countDays(int days, int[][] meetings) {
    int[][] sorted = meetings.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    long covered = 0;
    int reach = 0;
    for (int[] m : sorted) {
        int s = Math.max(m[0], reach + 1);
        if (m[1] >= s) {
            covered += m[1] - s + 1;
            reach = m[1];
        }
    }
    return (int) (days - covered);
}

C++

int countDays(int days, vector<vector<int>>& meetings) {
    vector<vector<int>> sorted = meetings;
    sort(sorted.begin(), sorted.end());
    long long covered = 0;
    int reach = 0;
    for (auto& m : sorted) {
        int s = max(m[0], reach + 1);
        if (m[1] >= s) {
            covered += m[1] - s + 1;
            reach = m[1];
        }
    }
    return (int) (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms