Total time covered
Add up the total time covered by at least one meeting, counting overlapping stretches only once, by sweeping through the start and end events. About 18 minutes.
Count each stretch once
Meetings [1, 4] and [2, 6] overlap. Adding their lengths, 3 and 4, gives 7, but the time from 1 to 6 is only 5 units. The shared stretch from 2 to 4 was counted twice.
Instead of lengths, look at time itself. Between two neighbouring events, the number of running meetings does not change. So each gap is either covered, if the count is above zero, or free.
Sweep and add the covered gaps
Build the events, a plus one at each start and a minus one at each end, and sort them. Walk through, remembering the previous event time and the running count.
At each event, if the count before it was above zero, the gap since the previous event is covered, so add its length. Then apply the change and move on. Each stretch of time is added at most once.
if cur > 0:
total += t - prev # something ran
prev = tTime 1: the first meeting starts. Nothing was covered before, so the total is 0.
Meetings [0, 10] and [5, 8]. How much time is covered?
- A10
- B13
- C15
Show the answer
10. The second meeting lies inside the first, so only 0 to 10 is covered.
Total covered time
You are given meetings, each as [start, end), occupying from start up to but not including end. Return the total length of time during which at least one meeting is running. Overlapping stretches count only once.
meetings = [[1, 4], [2, 6], [8, 9]] → 6
0 ≤ meetings.length ≤ 100,000 · 0 ≤ start < end ≤ 1,000,000,000