# Count Days Without Meetings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-days-without-meetings)
Canonical: https://scaleengineer.com/dsa/problems/count-days-without-meetings
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given a positive integer `days` representing the total number of days an employee is available for work (starting from day 1). You are also given a 2D array `meetings` of size `n` where, `meetings[i] = [start_i, end_i]` represents the starting and ending days of meeting `i` (inclusive).

Return the count of days when the employee is available for work but no meetings are scheduled.

**Note:** The meetings may overlap.

**Example 1:**

**Input:** days = 10, meetings = \[\[5,7\],\[1,3\],\[9,10\]\]

**Output:** 2

**Explanation:**

There is no meeting scheduled on the 4th and 8th days.

**Example 2:**

**Input:** days = 5, meetings = \[\[2,4\],\[1,3\]\]

**Output:** 1

**Explanation:**

There is no meeting scheduled on the 5th day.

**Example 3:**

**Input:** days = 6, meetings = \[\[1,6\]\]

**Output:** 0

**Explanation:**

Meetings are scheduled for all working days.

**Constraints:**

* `1 <= days <= 109`
* `1 <= meetings.length <= 105`
* `meetings[i].length == 2`
* `1 <= meetings[i][0] <= meetings[i][1] <= days`

# Approaches
## Brute Force using a Boolean Array
This approach simulates the days and meetings directly. We use a boolean array, where each index represents a day. We iterate through all meetings and mark the corresponding days in the array as busy. Finally, we count the number of days that were never marked.
**Time:** O(N * L + D), where N is the number of meetings, L is the average length of a meeting, and D is the total number of `days`. In the worst case, a meeting can span all `days`, making the complexity O(N * D). Given the constraints, this will result in a Time Limit Exceeded (TLE) error. · **Space:** O(D), where D is the total number of `days`. We need a boolean array of size `days + 1`. Given the constraint `days <= 10^9`, this will cause a Memory Limit Exceeded (MLE) error.
**Pros:** Simple to understand and implement.; Directly models the problem statement.
**Cons:** Extremely inefficient for large values of `days`.; Exceeds memory limits for `days` up to 10^9.; Exceeds time limits for `days` up to 10^9.
### Explanation
The core idea is to maintain a status for each day from 1 to `days`. A boolean array `isMeetingDay` of size `days + 1` is used for this purpose, where `isMeetingDay[i]` will be `true` if there's a meeting on day `i`, and `false` otherwise.

First, we initialize the entire array to `false`. Then, we iterate through each meeting interval `[start, end]` provided in the `meetings` array. For each interval, we run a nested loop from `start` to `end` and set `isMeetingDay[j] = true` for all `j` in this range. This process marks all days that are covered by at least one meeting.

After processing all the meetings, we perform a final scan through the boolean array from day 1 to `days`. We count how many indices `i` still have `isMeetingDay[i]` as `false`. This count represents the total number of days without any scheduled meetings.

```java
public int countDays(int days, int[][] meetings) {
    if (days <= 0) {
        return 0;
    }
    boolean[] hasMeeting = new boolean[days + 1];
    for (int[] meeting : meetings) {
        // Ensure meeting bounds are within the total days
        int start = Math.max(1, meeting[0]);
        int end = Math.min(days, meeting[1]);
        for (int i = start; i <= end; i++) {
            hasMeeting[i] = true;
        }
    }

    int freeDays = 0;
    for (int i = 1; i <= days; i++) {
        if (!hasMeeting[i]) {
            freeDays++;
        }
    }
    return freeDays;
}
```
### Algorithm
*   Create a boolean array `hasMeeting` of size `days + 1`, and initialize all its elements to `false`.
*   Iterate through each `meeting` in the input `meetings` array.
*   For each `meeting = [start, end]`, loop from `i = start` to `end` and set `hasMeeting[i] = true`.
*   Initialize a counter `freeDays` to 0.
*   Loop from `i = 1` to `days`.
*   If `hasMeeting[i]` is `false`, it means the day is free, so increment `freeDays`.
*   After the loop, return `freeDays`.

## Sort and Merge Intervals
A much more efficient approach is to treat this as an interval problem. The key insight is that we don't need to check every single day. Instead, we can find the total number of unique days covered by meetings and subtract this from the total `days`. To do this effectively, we first sort the meetings and then merge any overlapping or adjacent intervals into a set of disjoint intervals.
**Time:** O(N log N), where N is the number of meetings. The sorting step dominates the complexity. The subsequent single pass to merge intervals takes O(N) time. · **Space:** O(log N) or O(N), depending on the space used by the in-place sorting algorithm. For instance, Java's `Arrays.sort` for objects uses Timsort, which can take up to O(N) space in the worst case. No other significant auxiliary space is used.
**Pros:** Highly efficient and scalable.; Correctly handles all cases, including overlapping and adjacent meetings.; Works for large values of `days` as its complexity is independent of the magnitude of `days`.
**Cons:** Requires sorting, which adds an O(N log N) time cost.; Slightly more complex to implement than the brute-force approach.
### Explanation
The most efficient way to solve this problem is by focusing on the intervals themselves rather than individual days. The core idea is to merge overlapping intervals to find the total count of unique busy days, and then subtract this from the total number of days.

First, we sort the `meetings` array by their start day. This is a crucial step as it allows us to process meetings in chronological order and easily identify overlaps.

After sorting, we iterate through the meetings to merge them and calculate the total number of busy days. We start with the first meeting as our initial merged interval. Then, for each subsequent meeting, we check if it overlaps with our current merged interval. 
*   If it overlaps (i.e., its start time is before or at the end time of our merged interval), we extend our merged interval by updating its end time to the maximum of the two intervals' end times.
*   If it does not overlap, the previous merged interval is complete. We calculate its length and add it to a running total of `busyDays`. We then start a new merged interval with the current meeting.

After the loop, we add the length of the last merged interval to `busyDays`. The final answer is simply `days - busyDays`.

```java
import java.util.Arrays;

public int countDays(int days, int[][] meetings) {
    if (meetings.length == 0) {
        return days;
    }

    // Sort meetings by their start times
    Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));

    int busyDays = 0;
    int mergedStart = meetings[0][0];
    int mergedEnd = meetings[0][1];

    for (int i = 1; i < meetings.length; i++) {
        int[] currentMeeting = meetings[i];
        if (currentMeeting[0] <= mergedEnd) {
            // Overlap or adjacent, merge the intervals by extending the end
            mergedEnd = Math.max(mergedEnd, currentMeeting[1]);
        } else {
            // No overlap, the previous merged interval is complete
            busyDays += (mergedEnd - mergedStart + 1);
            // Start a new merged interval
            mergedStart = currentMeeting[0];
            mergedEnd = currentMeeting[1];
        }
    }
    
    // Add the last merged interval to the count of busy days
    busyDays += (mergedEnd - mergedStart + 1);

    return days - busyDays;
}
```
### Algorithm
*   Handle the edge case: if `meetings` is empty, return `days`.
*   Sort the `meetings` array based on the start times in ascending order.
*   Initialize `totalBusyDays = 0`.
*   Initialize `mergedStart` and `mergedEnd` with the start and end of the first meeting.
*   Iterate through the sorted `meetings` array from the second meeting.
*   For the current `meeting = [start, end]`:
    *   If `start` is less than or equal to `mergedEnd`, there is an overlap. Extend the current merged interval by updating `mergedEnd = max(mergedEnd, end)`.
    *   If `start` is greater than `mergedEnd`, there is no overlap. The previous merged interval is complete. Calculate its duration (`mergedEnd - mergedStart + 1`) and add it to `totalBusyDays`. Then, start a new merged interval by setting `mergedStart = start` and `mergedEnd = end`.
*   After the loop finishes, add the duration of the last merged interval to `totalBusyDays`.
*   The number of free days is `days - totalBusyDays`. Return this value.

# Solutions
### Java

```java
class Solution {
public
  int countDays(int days, int[][] meetings) {
    Arrays.sort(meetings, (a, b)->a[0] - b[0]);
    int ans = 0, last = 0;
    for (var e : meetings) {
      int st = e[0], ed = e[1];
      if (last < st) {
        ans += st - last - 1;
      }
      last = Math.max(last, ed);
    }
    ans += days - last;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countDays(int days, vector<vector<int>> &meetings) {
    sort(meetings.begin(), meetings.end());
    int ans = 0, last = 0;
    for (auto &e : meetings) {
      int st = e[0], ed = e[1];
      if (last < st) {
        ans += st - last - 1;
      }
      last = max(last, ed);
    }
    ans += days - last;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int: meetings . sort() ans = last = 0 for st, ed in meetings: if last < st: ans += st - last - 1 last = max(last, ed) ans += days - last return ans

```