3169. Count Days Without Meetings

Description

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 4^th and 8^th days.

Example 2:

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

Output: 1

Explanation:

There is no meeting scheduled on the 5^thday.

Example 3:

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

Output: 0

Explanation:

Meetings are scheduled for all working days.

Constraints:

1 <= days <= 10⁹
1 <= meetings.length <= 10⁵
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days

Solutions

Solution 1: Sorting

We can sort all the meetings by their start time, and use a variable last to record the latest end time of the previous meetings.

Then we traverse all the meetings. For each meeting \((st, ed)\), if last < st, it means that the time period from last to st is a time period when employees can work and no meetings are scheduled. We add this time period to the answer. Then we update last = max(last, ed).

Finally, if last < days, it means that there is a time period after the end of the last meeting when employees can work and no meetings are scheduled. We add this time period to the answer.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Where \(n\) is the number of meetings.

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

func countDays(days int, meetings [][]int) (ans int) {
    sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
    last := 0
    for _, e := range meetings {
        st, ed := e[0], e[1]
        if last < st {
            ans += st - last - 1
        }
        last = max(last, ed)
    }
    ans += days - last
    return
}

function countDays(days: number, meetings: number[][]): number {
    meetings.sort((a, b) => a[0] - b[0]);
    let [ans, last] = [0, 0];
    for (const [st, ed] of meetings) {
        if (last < st) {
            ans += st - last - 1;
        }
        last = Math.max(last, ed);
    }
    ans += days - last;
    return ans;
}

3169. Count Days Without Meetings

Description

Solutions

Solution 1: Sorting

Comments