algorithm - 重新安排 session 问题 : Where maximum rearrangement can go upto a value k

Question

我的一个 friend 最近在接受 Tech 采访时遇到了这个问题。
问题名称 - 长假

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, 7, 8, 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-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 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.

不幸的是，我无法将问题映射到标准问题。我已经尝试了我自己的天真实现，它似乎对给定的输入工作正常(必须为边缘情况重新制定策略)
这是我的实现

import java.util.ArrayList;
import java.util.Iterator;
class Test {

public static void main(String args[]) {
    Test T  = new Test();
    int  n = 4;
    int k = 2;
    int start[] = {4, 6, 7, 10};
    int end[] = {5, 7, 8, 11};
    int t = 15;
    System.out.println(T.findBreakDuration(n, k, start, end, t));
}

int findBreakDuration(int n, int k, int start[], int end[], int t) {
    boolean meetings[] = new boolean[t]; // false means empty slot
    int i = 0;
    while (i < n) {
        for (int j = start[i]; j < end[i]; j++)
            meetings[j] = true;
        i++;
    }

    
    ArrayList<Integer> emptySlots = new ArrayList<Integer>();
    int count = 0;
    for (i  = 0; i < meetings.length; i++) {
        if (!meetings[i])
            count++;
        else {
            if (count > 0) {
                emptySlots.add(count);
                count = 0;
            }

        }
    }
    if (count > 0)
        emptySlots.add(count);
    
    if(emptySlots.size()<=1)
        return -1;
    int maxSoFar = Integer.MIN_VALUE;
    for(i = 0;i<emptySlots.size();i++){
        int e = emptySlots.get(i);
        if(e<=k){
            if(i==0){
                int increasedRight = e + emptySlots.get(i+1);
                if(maxSoFar<increasedRight)
                    maxSoFar = increasedRight;
            }
            else if(i==emptySlots.size()-1)
            {
                int increasedLeft = e + emptySlots.get(i-1);
                if(maxSoFar<increasedLeft)
                    maxSoFar = increasedLeft;
            }
            else{
                int increasedLeft = e + emptySlots.get(i-1);
                int increasedRight = e + emptySlots.get(i+1);

                if(maxSoFar<increasedLeft)
                    maxSoFar = increasedLeft;
                if(maxSoFar<increasedRight)
                    maxSoFar = increasedRight;
            }
        }
    }
    return maxSoFar; // Output : 6, in this case
}
} 

上述代码的简短描述 -
我只是在跟踪空插槽，并在允许的重新排列(即 <=k)后比较最大可用插槽。最终最大值为我提供了空槽序列的最大可能长度或最大持续时间。
我知道这是一个非常幼稚的实现，我相信有一种更好、更优雅的方法来解决这个问题。我有一种非常强烈的感觉，我在这里错过了一些基本的东西。有没有办法优雅地解决这个问题？

Answer 1

工作流程确实非常优雅。

1) 从作业中提取空位，注意连续演示之间有 0 个空位。

slotLengths = { 4, 1, 0, 2, 4 }

2)对于给定的k，比较slotLengths的k+1个相邻值之和.因此，对于 k=2，比较以下总和:

 { 4, 1, 0 }

 { 1, 0, 2 }

 { 0, 2, 4 }

3)最后一个获胜，因此将这些演示文稿移到任一侧。