3430. Count Days Without Meetings¶

Difficulty: Medium

3430. Count Days Without Meetings

Medium

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

Solution¶

class Solution {
    static class Pair {
        int start, end;
        public Pair(int start, int end) {
            this.start = start;
            this.end = end;
        }
        @Override
        public String toString() {
            return "(" + start + " " + end + ")";
        }
    }
    static class sorting implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            return Integer.compare(first.start, second.start);
        }
    }
    public int countDays(int days, int[][] meetings) {
        int n = meetings.length;
        int m = meetings[0].length;
        ArrayList<Pair> res = new ArrayList<>();
        for(int current[] : meetings) {
            int start = current[0], end = current[1];
            res.add(new Pair(start, end));
        }
        Collections.sort(res, new sorting());
        int current = 1, total = 0;
        for(int i = 0; i < res.size(); i++) {
            if(i == 0) {
                if(res.get(i).start != 1) {
                    total += res.get(i).start - current;
                    current = res.get(i).end;
                    continue;
                }
            }
            int calc = res.get(i).start - current - 1;
            if(calc > 0) total += calc;
            current = Math.max(current, res.get(i).end);
        }
        if(days - current > 0) total += days - current;
        return total;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here