Count Days Without Meetings

return number of days when person has no meeting

Count Days Without Meetings

Problem

You are given a positive integer days. It is the total number of days an employee can work, starting from day 1.

You are also given a 2D array meetings. Each meetings[i] = [start, end] is a meeting that runs from day start to day end. Both days are included.

Return the number of days when the employee is free and has no meeting.

The meetings may overlap.

Examples

Example 1

Input: days = 10, meetings = [[5,7],[1,3],[9,10]]
Output: 2

• Meetings cover days 1-3, 5-7 and 9-10.
• Day 4 and day 8 are free.

Example 2

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

• The two meetings overlap. Together they cover days 1-4.
• Day 5 is free.

Example 3

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

• One meeting covers all 6 days.

Constraints

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

Main Idea

days can be as big as 10^9. So we cannot make an array with one cell for each day. It would use too much memory and time.

Instead, we work with the meetings. There are at most 10^5 of them.

The idea is to merge overlapping meetings into bigger blocks. Then we count the busy days and subtract them from days.

Steps

• Sort the meetings by their start day.
• Keep a list called unOverlapped that holds the merged meetings. Start with the first meeting.
• For each next meeting, compare it with the last merged meeting:
  • Overlap: If the new meeting starts on or before the last end (meet[0] <= lastEnd), the two meetings join. We extend the end to the bigger of the two ends.
  • No overlap: We add the new meeting as a new block.
• For each merged block, the busy days are end - start + 1. We add them all.
• The answer is days - busyDays.

Why + 1? Both the start day and the end day are included. For example, [5, 7] covers days 5, 6 and 7. That is 3 days, and 7 - 5 + 1 = 3.

Solution: Sort and Merge

var countDays = function (days, meetings) {
    // sort meetings by start day
    meetings.sort((a, b) => a[0] - b[0]);

    // merged meetings, start with the first one
    let unOverlapped = [meetings[0]];

    for (let i = 1; i < meetings.length; i++) {
        let meet = meetings[i];
        let lastEnd = unOverlapped[unOverlapped.length - 1][1];

        if (meet[0] <= lastEnd) {
            // overlap, so extend the last block
            unOverlapped[unOverlapped.length - 1][1] = Math.max(lastEnd, meet[1]);
        } else {
            // no overlap, so start a new block
            unOverlapped.push(meet);
        }
    }

    // count the busy days
    let busyDays = 0;

    for (let meet of unOverlapped) {
        busyDays += meet[1] - meet[0] + 1;
    }

    // free days = total days - busy days
    return days - busyDays;
};

Tip: In your code, the variable leastStart is never used, so I removed it. Also, unOverlapped[unOverlapped.length - 1][1] = ... changes the original meeting array, because both point to the same object. This is fine for this problem. If you need to keep the input as it was, push a copy: unOverlapped.push([...meet]).

How the Code Works

Step 1: Sort the meetings

• meetings.sort((a, b) => a[0] - b[0]) puts meetings in order of start day.
• After sorting, overlapping meetings are next to each other. So we only need to compare with the last merged block.

Step 2: Start the merged list

• unOverlapped starts with the first meeting.
• The problem says meetings.length >= 1, so this is safe.

Step 3: Merge the meetings

• lastEnd is the end day of the last merged block.
• If meet[0] <= lastEnd, the new meeting starts inside the block (or touches it). We set the block's end to Math.max(lastEnd, meet[1]).
  • We need Math.max, because the new meeting can be inside the block. For example, block [1, 10] and meeting [2, 5]. The end must stay 10.
• Otherwise, there is a gap before this meeting. We push it as a new block.

Step 4: Count the busy days

• For each block, we add end - start + 1.
• Merged blocks do not overlap, so no day is counted twice.

Step 5: Return the free days

• days - busyDays is the answer.

Dry Run

Let us take days = 10 and meetings = [[5,7],[1,3],[9,10]].

After sorting: [[1,3],[5,7],[9,10]]

Busy days:

• [1,3] gives 3 - 1 + 1 = 3
• [5,7] gives 7 - 5 + 1 = 3
• [9,10] gives 10 - 9 + 1 = 2
• Total = 3 + 3 + 2 = 8

Free days: 10 - 8 = 2.

Now let us take days = 5 and meetings = [[2,4],[1,3]].

After sorting: [[1,3],[2,4]]

• Busy days = 4 - 1 + 1 = 4.
• Free days = 5 - 4 = 1.

Complexity

• Time Complexity: O(m log m)
  • m is the number of meetings.
  • Sorting takes O(m log m).
  • The merge loop and the counting loop each take O(m).
  • Sorting is the biggest part.
• Space Complexity: O(m)
  • The unOverlapped list can hold up to m blocks, when no meetings overlap.
  • Sorting may also use some extra space, depending on the language.

Comparison

Summary

• days can be up to 10^9, so we cannot check each day. We work with the meetings instead.
• First, sort the meetings by start day.
• Then merge overlapping meetings into blocks. Use Math.max for the end day.
• Each block covers end - start + 1 busy days. The + 1 is needed because both days are included.
• The answer is days - busyDays.
• The solution runs in O(m log m) time and uses O(m) space.