Solution: Count Days Without Meetings

Let’s solve the Count Days Without Meetings using the Merge Intervals pattern.

We'll cover the following

Statement

You are given a positive integer, days, which represents the total number of days an employee is available for work, starting from day 11. You are also given a 2D array, meetings, where each entry meetings[i] =[starti,endi]= [start_i, end_i] indicates that a meeting is scheduled from day startistart_i to day endiend_i (both inclusive).

Your task is to count the days when the employee is available for work but has no scheduled meetings.

Note: The meetings may overlap.

Constraints:

  • 1≤1 \leq days ≤100000\leq 100000

  • 1≤1 \leq meetings.length ≤1000\leq 1000

  • meetings[i].length ==2==2

  • 1≤1 \leq meetings[i][0] ≤\leq meetings[i][1] ≤\leq days

Solution

The core idea of this solution is to merge overlapping meetings into continuous intervals to efficiently track the occupied days. We begin by sorting the meetings to process them sequentially. As we iterate, we merge overlapping meetings while counting the occupied days whenever gaps appear. Finally, subtracting the total occupied days from the available days gives the number of free days.

Using the intuition above, we implement the algorithm as follows:

  1. First, sort the meetings based on their start time to process them in order.

  2. Initialize a variable, occupied, with 00 to count the days when the employee has scheduled meetings.

  3. Initialize two variables, start and end, with the first meeting’s start and end times. These variables define the beginning and end of the merged meeting interval to efficiently track continuously occupied periods.

  4. Iterate through the remaining meetings:

    1. If a meeting overlaps with the current merged meeting, extend the end time to merge it into the existing interval.

    2. Otherwise, add the days of the merged meeting to occupied asoccupied=occupied+(end−start+1)occupied = occupied + (end - start + 1). Then, update the start and end for the next interval.

  5. After the loop, add the days of the last merged interval to occupied.

  6. Return the difference between days and occupied (days−occupieddays - occupied), representing the number of days when the employee is available for work but has no scheduled meetings.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.