Google Phone screen

Round 1

Questions: Reschedule k meetings to find maximum break time. For example, there are n = 4 presenters scheduled for the course of the event which begins at time 0 and ends at time t = 15. The meetings start at times start = [4, 6, 7, 10] and end at times finish = [5, 7, 8, 11]. You can rearrange up to k = 2 meetings. In this case, we have 4 periods without speakers scheduled: [0-3], [5], [8-9], [11-14]. The meeting ends after hour 14. If the first meeting is shifted to an hour later, a break is created from 0 to 5 (5 hours). If the last speech is moved up to 8, it will end at 9, leaving a break from 9 to 15. There is no point in moving the middle two speeches in this case. The longest break that can be achieved is 15 - 9 = 6 hours by moving the last speech two hours earlier. NOTE: We cannot change the order of events.

Constraints:

• 1 ≤ n ≤ 10^5 (number of events)
• 0 ≤ k ≤ n (number of reschedules allowed)
• 1 ≤ t ≤ 10^9 (total duration of the day)
• 0 ≤ start[i] < finish[i] ≤ t for all i (start and end times of events)