LC: Meeting Scheduler - spiralgo/algorithms GitHub Wiki

Meeting Scheduler

The Essence:

The basis for a solution to this problem should implement the following logic:

1. We should find two intervals that intersect, it doesn't matter to whom these intervals belong. (If two intervals intersect, they can not belong to the same person according to constraints)
2. We should calculate the duration of this intersection.
3. If that duration is longer than the sought duration, then return the beginning time of this interval and the given duration added with this start time (as end time).

The given intervals are not sorted. To find the earliest time, we need to somehow process these in ascending order.

Details:

In a common interval, the interval duration is given by min(end1, end2) - max(start1, start2). When processing the starting times in sorted order, if this duration is longer than k, then the interval [max(start1, start2), max(start1, start2)+k] should be returned. To process the intervals in a sorted manner, the given lists can be sorted or a priority queue can be used.

For priority queue, comparison of polled and peeked intervals can be used. For sorting, two pointers approach is the best.

The code of these approaches can be found here.