Medium

Count Days Without Meetings

LAB

Given days numbered 1 through days and meeting intervals [start,end], return how many days have no meeting scheduled.

EXAMPLES

Example 1

Input
{
  "days": 10,
  "meetings": [
    [
      5,
      7
    ],
    [
      1,
      3
    ],
    [
      9,
      10
    ]
  ]
}

Output
2

FUNCTION SHAPE

days: intmeetings: intMatrix→int

SOLUTION NOTE

The easiest explanation is to walk through the example. Sorting meeting gives [1,3], [5,7], [9,10].

We basically want to count the gaps of days between meetings. This is what max(0, s-day-1) does. S-day-1 can be negative because the intervals can overlap. Also the case where the current end time is less than the previous end time (day) is possible, think about [1,6], [2,3], so we need to take the max, to keep day = 6. Don't forget about the last gap days - day.

Reveal reference solution +

pythonREFERENCE

def countDays(self, days: int, meetings: List[List[int]]) -> int:
    res = day = 0
    for s, e in sorted(meetings):
        res += max(0, s - day - 1)
        day = max(day, e)
    return res + (days - day)

TimeO(n log n)

SpaceO(1)

Open on LeetCode ↗