Practice/Google/Leetcode 3169. Count Days Without Meetings

Leetcode 3169. Count Days Without Meetings

CodingMust

Problem

You are given an integer representing the total number of days in a planning period, numbered from 1 to days inclusive. You are also given a list of meeting intervals, where each interval is represented as [start, end] indicating that a meeting occupies all days from start to end inclusive.

Your task is to determine how many days in the range [1, days] have no meetings scheduled. Note that meetings may overlap or touch each other, and you need to account for this when calculating free days.

Requirements

1. Calculate the total number of days covered by at least one meeting
2. Handle overlapping and adjacent meeting intervals correctly
3. Return the count of days that are completely free (not covered by any meeting)
4. The solution must be efficient enough to handle very large values of days (up to 10^9)

Constraints

• 1 ≤ days ≤ 10^9
• 0 ≤ meetings.length ≤ 5 × 10^4
• meetings[i].length == 2
• 1 ≤ meetings[i][0] ≤ meetings[i][1] ≤ days
• Time complexity should be O(n log n) where n is the number of meetings
• Space complexity should be O(1) or O(n)

Examples

Example 1:

Input: days = 10, meetings = [[5,7],[1,3],[9,10]] Output: 2 Explanation: The meetings cover days 1-3, 5-7, and 9-10. Days 4 and 8 are free.

Example 2:

Input: days = 20, meetings = [[1,10],[5,15],[8,18]] Output: 2 Explanation: These overlapping meetings merge into a single continuous block covering days 1-18. Only days 19 and 20 are free.

Example 3:

Input: days = 5, meetings = [] Output: 5 Explanation: With no meetings scheduled, all 5 days are free.