Maximizing Networking Break

Problem Preview

"You are organizing an event where there will be a number of presenters. The event starts at time 0 and time be allocated for networking at any time during the event when there is not a presentation being made. The presentations may not overlap as they are in the same room, but this allows them to run consecutively, without breaks. While the order of speeches cannot be changed, there is a maximum number given that indicates how many speeches may be rescheduled. Your goal is to maximize the length of the longest networking period you can arrange. 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, 8, 11, 11]. You can rearrange up to k = 2 meetings. Green cells are free, marked with the hour number, and blue cells have a presentation scheduled, marked with presentation number. In this case, we have 4 periods without speakers scheduled: [(0-3), (5-8), (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 to 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 to two hours earlier. The two options are illustrated below. Option 1: Option 2: "