3169. Count Days Without Meetings

Description

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 4^th and 8^th days.

Example 2:

Input: days = 5, meetings = [[2,4],[1,3]]

Output: 1

Explanation:

There is no meeting scheduled on the 5^th 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

 

Solutions

Solution: Sorting

• Time complexity: O(nlogn)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} days
 * @param {number[][]} meetings
 * @return {number}
 */
const countDays = function (days, meetings) {
  let lastEnd = 0;
  let result = 0;

  meetings.sort((a, b) => a[0] - b[0]);

  for (const [start, end] of meetings) {
    if (start > lastEnd) {
      result += start - lastEnd - 1;
      lastEnd = end;
    } else {
      lastEnd = Math.max(end, lastEnd);
    }
  }

  return result + days - lastEnd;
};