LeetCode 3169. Count Days Without Meetings

Problem Statement

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.

Test Cases

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 <= 10^9
1 <= meetings.length <= 10^5
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days

Intuition

We have intervals given to us which will have meetings started at starti time and will end at endi time. If we manually draw a line and track each and every meeting start and end time, we could see the gaps where the person will be free. So if we are able to calculate this gaps, then we will get the free person.

Approach

• Sort the given 2D array based on start time. Why start time, other wise we couldn't properly merge the array and may need to do repeated calculations to merge the intervals properly. Example Test case : [1,3], [6,8], [2,9]
• We would check if the starting of the current meeting is greater than previous meeting end, if yes, we could confirm there is a gap and can add that value.
• Update the latestEnd with the maximum end value of the interval.
• There might be some more days left with respect to the previous meeting end. Calculate that gap as well to get the free time.

Complexity

• Time complexity:

  O(NlogN) + O(N)

• Space complexity:

  O(1), assuming the sorting takes constant or if sorting considered then O(logn) space

Code

class Solution {
    public int countDays(int days, int[][] meetings) {
        if (meetings == null || meetings.length == 0) {
            return days;
        }
        int meetingArrayLength = meetings.length;
        Arrays.sort(meetings, new MeetingsArraySort());
        int latestEnd = 0;
        int freeDays = 0;
        for (int [] meeting : meetings) {
            int start = meeting[0];
            int end = meeting[1];
            if (start > latestEnd + 1) {
                freeDays += start - latestEnd - 1;
            }
            latestEnd = Math.max(latestEnd, end);
        }
        freeDays += days - latestEnd;
        return freeDays;
    }
}

class MeetingsArraySort implements Comparator<int []> {
    @Override
    public int compare(int [] m1, int [] m2) {
        return Integer.compare(m1[0], m2[0]);
    }
}