Count Days Without Meetings

Medium Intervals Basics Original on LeetCode

Reported atSwiggy

Count Days Without Meetings is a medium intervals problem solved with the basics pattern. The best approach, optimal (sort and sweep merged blocks), runs in O(m log m) time and O(log m) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (mark every day) up.

Problem

An employee is available for days days, numbered from 1 to days. You are also given meetings, where meetings[i] = [start_i, end_i] means a meeting occupies every day from start_i to end_i, both included.

Meetings may overlap. Return how many days in the range 1..days have no meeting scheduled at all.

Examples

Example 1

Input
days = 8, meetings = [[2, 3], [6, 7], [3, 4]]
Output
3
Why
Days 2, 3, 4, 6 and 7 are busy, so days 1, 5 and 8 are free.

Example 2

Input
days = 5, meetings = [[1, 5]]
Output
0
Why
A single meeting covers the whole period.

Example 3

Input
days = 7, meetings = [[4, 4], [2, 2]]
Output
5
Why
Only days 2 and 4 are busy; days 1, 3, 5, 6 and 7 are free.

Constraints

  • 1 <= days <= 10^9
  • 1 <= meetings.length <= 10^5
  • meetings[i] = [start_i, end_i] with 1 <= start_i <= end_i <= days

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (mark every day)O(days + total meeting length)O(days)
Optimal (sort and sweep merged blocks)O(m log m)O(log m)

1Brute force (mark every day)

TimeO(days + total meeting length)Each meeting walks over all its days, and the final count walks over every day.
SpaceO(days)One flag per day; impossible when days is 10^9.

Keep one flag per day. For every meeting, mark each day in its range as busy. Then count the days that were never marked.

  1. Create a boolean array busy of size days + 1.
  2. For each meeting [s, e], set busy[d] = true for d from s to e.
  3. Count d in 1..days with busy[d] == false.
class Solution {
    public int countDays(int days, int[][] meetings) {
        boolean[] busy = new boolean[days + 1];
        for (int[] m : meetings) {
            for (int d = m[0]; d <= m[1]; d++) {
                busy[d] = true;
            }
        }
        int free = 0;
        for (int d = 1; d <= days; d++) {
            if (!busy[d]) free++;
        }
        return free;
    }
}

2Optimal (sort and sweep merged blocks)

TimeO(m log m)Sorting the m meetings dominates; the sweep is linear.
SpaceO(log m)Only the sort's internal stack; the sweep uses two variables.

Sort the meetings by start day and sweep them while remembering lastEnd, the latest busy day so far. If a meeting starts after lastEnd + 1, the days strictly between are free. Extending lastEnd with max merges overlapping and nested meetings automatically. At the end, the days after lastEnd are free too.

  1. Sort meetings by start.
  2. Set lastEnd = 0 and free = 0.
  3. For each [s, e]: if s > lastEnd + 1, add s - lastEnd - 1 to free; then lastEnd = max(lastEnd, e).
  4. Add days - lastEnd to free and return it.
class Solution {
    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
        int lastEnd = 0;
        int free = 0;
        for (int[] m : meetings) {
            if (m[0] > lastEnd + 1) {
                free += m[0] - lastEnd - 1;
            }
            lastEnd = Math.max(lastEnd, m[1]);
        }
        free += days - lastEnd;
        return free;
    }
}

Edge cases to test

  • Overlapping meetings must not be subtracted twice
  • Meetings that touch end to start, like [1, 3] and [4, 6], leave no free day between them
  • One meeting nested inside another
  • Free days before the first meeting and after the last one
  • days is huge (10^9), so you cannot keep one flag per day

Hints

Hint 1

Overlaps are the hard part. What happens if you first merge overlapping meetings into disjoint blocks?

Hint 2

Sort meetings by start day and keep the latest end day seen so far.

Hint 3

A gap exists when a meeting starts more than one day after that latest end; also count the days after the final end.

FAQ

What is the best time complexity for Count Days Without Meetings?

Optimal (sort and sweep merged blocks) runs in O(m log m) time and O(log m) extra space. Sorting the m meetings dominates; the sweep is linear.

Which pattern does Count Days Without Meetings use?

It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.

Is there a brute force solution for Count Days Without Meetings?

Yes. Brute force (mark every day) takes O(days + total meeting length) time and O(days) space. Keep one flag per day.

Which edge cases should I test for Count Days Without Meetings?

Overlapping meetings must not be subtracted twice; Meetings that touch end to start, like [1, 3] and [4, 6], leave no free day between them; One meeting nested inside another; Free days before the first meeting and after the last one; days is huge (10^9), so you cannot keep one flag per day.