3169. Count Days Without Meetings

[mah-shamim]

Topics: Array, Sorting

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

Hint:

1. Merge the overlapping meetings and sort the new meetings timings.
2. Return the sum of difference between the end time of a meeting and the start time of the next meeting for all adjacent pairs.

[mah-shamim]

We need to determine the number of days an employee is available for work but has no meetings scheduled. The approach involves merging overlapping meetings and calculating the gaps between these merged meetings.

Approach

1. Sort Meetings: First, we sort the meetings based on their start times to handle overlaps efficiently.
2. Merge Overlapping Meetings: We then merge overlapping or adjacent meetings into non-overlapping intervals. This helps in accurately calculating the total days covered by meetings.
3. Calculate Covered Days: Sum the days covered by each merged interval.
4. Compute Result: Subtract the total covered days from the given total days to get the count of days without any meetings.

Let's implement this solution in PHP: 3169. Count Days Without Meetings

<?php
/**
 * @param Integer $days
 * @param Integer[][] $meetings
 * @return Integer
 */
function countDays($days, $meetings) {
    // Sort the meetings by their start time
    usort($meetings, function($a, $b) {
        return $a[0] - $b[0];
    });

    // Merge overlapping intervals
    $merged = array();
    foreach ($meetings as $meeting) {
        if (empty($merged)) {
            $merged[] = $meeting;
        } else {
            $lastIdx = count($merged) - 1;
            $last = &$merged[$lastIdx];
            if ($meeting[0] <= $last[1]) {
                // Merge the intervals
                $last[1] = max($last[1], $meeting[1]);
            } else {
                $merged[] = $meeting;
            }
        }
    }

    // Calculate the total covered days
    $covered = 0;
    foreach ($merged as $interval) {
        $covered += $interval[1] - $interval[0] + 1;
    }

    // The result is total days minus covered days
    return $days - $covered;
}

// Example test cases
echo countDays(10, [[5,7],[1,3],[9,10]]); // Output: 2
echo "\n";
echo countDays(5, [[2,4],[1,3]]); // Output: 1
echo "\n";
echo countDays(6, [[1,6]]); // Output: 0
?>

Explanation:

1. Sorting: By sorting the meetings based on their start times, we ensure that we can sequentially process each meeting and merge overlaps as we encounter them.
2. Merging Intervals: We iterate through the sorted meetings and merge them if they overlap or are adjacent. This is done by checking if the start of the current meeting is within the range of the last merged interval. If so, we extend the end of the merged interval to the maximum end of both intervals.
3. Summing Covered Days: For each merged interval, we calculate the number of days it covers by subtracting the start from the end and adding 1 (since both start and end days are inclusive).
4. Result Calculation: The final result is obtained by subtracting the total covered days from the given total days, giving the count of days without any meetings.

This approach efficiently handles up to 100,000 meetings and works within the constraints, ensuring optimal performance.

[topugit]

Thanks for solving the problem of "Count Days Without Meetings"

[mah-shamim]

Thanks