会议重排问题：最大重排可以达到值k

Question

我的一个朋友最近在一次技术采访中遇到了这个问题。

问题名称- 长时间休息

您正在组织一个活动，将有很多演示者。该事件从时间0开始，并且在事件期间的任何时间（没有演示文稿）都被分配用于联网。演示文稿可能不会重叠，因为它们在同一个房间中，但这使它们可以连续运行而不会中断。虽然语音顺序无法更改，但有一个最大数目可以指示可以重新安排多少语音。您的目标是最大程度地安排您可以安排的最长联网时间。例如，有n = 4个主持人安排了该活动的过程，该活动从时间0开始，在时间t = 15结束。会议在时间start = [4，6，7，10]开始，在时间结束时结束= [5、7、8、11]。您最多可以重新安排k = 2个会议。绿细胞是自由的

在这种情况下，我们有4个时段未安排发言人：[（0-3），（5），（8-9），（11-14）]。会议在14小时后结束。如果将第一次会议移至一个小时后，则会在0到5、5个小时之间创建休息时间。如果将最后一个语音移至8，它将在9结束，从9中断到15。在这种情况下，将中间的两个语音移到没有意义。通过将最后一个语音移到两个小时之前，可以实现的最长间隔是15-9 = 6小时。这两个选项如下所示。

不幸的是，我无法将问题映射到一个标准的问题上。我已经尝试过自己的幼稚实现，对于给定的输入似乎效果很好（必须针对极端情况重新制定策略）

这是我的实现

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，比较 的 k+1 个相邻值的总和slotLengths。因此，对于 k=2，比较以下总和：

 { 4, 1, 0 }

 { 1, 0, 2 }

 { 0, 2, 4 }

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