3169. Count Days Without Meetings

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

Approach 01:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int countDays(int totalDays, vector<vector<int>>& meetings) {
        if (meetings.empty()) 
            return totalDays;
  
        sort(meetings.begin(), meetings.end());
        vector<vector<int>> mergedMeetings;
        
        for (const vector<int>& meeting : meetings) {
            if (mergedMeetings.empty()) {
                mergedMeetings.push_back(meeting);
            } else {
                int lastStart = mergedMeetings.back()[0];
                int lastEnd = mergedMeetings.back()[1];
                int currentStart = meeting[0];
                int currentEnd = meeting[1];

                if (currentStart <= lastEnd + 1) {
                    mergedMeetings.back()[1] = max(lastEnd, currentEnd);
                } else {
                    mergedMeetings.push_back(meeting);
                }
            }
        }

        int freeDays = 0;
        int previousEnd = 0;

        for (const vector<int>& meeting : mergedMeetings) {
            int start = meeting[0];
            int end = meeting[1];

            freeDays += start - previousEnd - 1;
            previousEnd = max(previousEnd, end);
        }

        freeDays += totalDays - previousEnd;

        return freeDays;
    }
};

from typing import List

class Solution:
    def countDays(self, totalDays: int, meetings: List[List[int]]) -> int:
        if not meetings:
            return totalDays

        meetings.sort()
        mergedMeetings = []

        for meeting in meetings:
            if not mergedMeetings:
                mergedMeetings.append(meeting)
            else:
                lastStart, lastEnd = mergedMeetings[-1]
                currentStart, currentEnd = meeting

                if currentStart <= lastEnd + 1:
                    mergedMeetings[-1] = [lastStart, max(lastEnd, currentEnd)]
                else:
                    mergedMeetings.append(meeting)

        freeDays = 0
        previousEnd = 0

        for start, end in mergedMeetings:
            freeDays += start - previousEnd - 1
            previousEnd = max(previousEnd, end)

        freeDays += totalDays - previousEnd

        return freeDays

Time Complexity:

• Sorting:

  The meetings are sorted based on their start times, which takes \( O(m \log m) \), where \( m \) is the number of meetings.

• Merging Intervals:

  Each meeting is processed once while merging, leading to \( O(m) \) complexity.

• Calculating Free Days:

  Iterating over the merged intervals takes \( O(m) \).

• Total Time Complexity:

  The overall time complexity is \( O(m \log m) \).

Space Complexity:

• Sorting Overhead:

  The sorting algorithm typically requires \( O(m) \) auxiliary space.

• Merged Meetings Storage:

  A separate list is maintained for merged intervals, taking \( O(m) \) space.

• Total Space Complexity:

  The overall space complexity is \( O(m) \).