Проблема перестановки собраний: где максимальная перестановка может доходить до значения k

Question

Мой друг недавно столкнулся с этой проблемой в техническом интервью.

Название проблемы - Длинный перерыв

Вы организуете мероприятие, на котором будет несколько докладчиков. Событие начинается в момент времени 0, и время будет выделено для сеть в любое время во время мероприятия, когда нет презентация делается. Презентации не могут перекрываться, поскольку они в той же комнате, но это позволяет им работать последовательно, без брейки. Хотя порядок выступлений не может быть изменен, существует максимальное число, которое указывает, сколько речей может быть перенесено. Ваша цель - максимизировать длину самого длинного Сетевой период вы можете организовать. Например, есть n = 4 ведущие запланированы на ход мероприятия, которое начинается во время 0 и заканчивается в момент времени t = 15. Встречи начинаются в моменты времени start = [4, 6, 7, 10] и заканчиваются время от времени отделкой = [5, 7, 8, 11]. Вы можете переставить к = 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). Окончательное максимальное значение дает мне максимально возможную длину или максимальную продолжительность последовательности пустых слотов. </em>

Я знаю, что это очень наивная реализация, и я уверен, что есть лучший и элегантный способ решения проблемы. У меня очень сильное чувство, что я упускаю что-то элементарное здесь. Есть ли способ решить эту проблему элегантным способом?

Answer 1

По предложению @ ingen

Шаги для решения: -

Шаг 1: создание списка пустых временных интервалов

Шаг 2: Найти подмассив размера k + 1 с максимальной суммой

Я хотел бы добавить только одну вещь.

Вместо того, чтобы вычислять сумму подмассива для каждого начального элемента, мы можем поддерживать окно размера k + 1 и продолжать добавлять элементы спереди, удаляя элементы сзади. Это даст нам общую временную сложность O (n)

Сохранить переменную, чтобы отслеживать сумму для этого окна. Максимальное значение этой переменной - это ответ, который мы ищем.

int findMaximumEmptyTimeSlot(List<Integer> emptySlots, int k){

    if(emptySlots.size() == 0) return 0;

    int maxSum = 0;
    int sum = 0;
    for(int i = 0; i < emptySlots.size() && i < k+1; i++)
        sum += emptySlots.get(i);

    maxSum = Math.max(sum, maxSum);

    for(int i = k+1; i < emptySlots.size(); i++){
        int newidx = i;
        int remidx = i - (k+1);

        sum = sum - emptySlots.get(remidx) + emptySlots.get(newidx);

        maxSum = Math.max(sum, maxSum);
    }

    return maxSum;
}

Answer 2

Проблема с проверкой e <= k, которая не нужна. После вычисления пустых слотов, Поскольку вы можете максимально переместить две встречи, вам необходимо сложить три последовательных пустых слота и взять максимум этого. Это связано с тем, что два собрания создают максимум три пустых слота. До и после каждого слота и слот между ними. </p>

for(i = 0;i<emptySlots.size()-2;i++){
      int newmax = emptySlots.get(i)+emptySlots.get(i+1)+emptySlots.get(i+2);            
      if(max<newmax) max=newmax;
      }

Answer 3

Я реализовал подход, предложенный @ ingen

1) Извлеките пустые места из задания, отметьте, что последовательные презентации имеют 0 пустых интервалов между ними.

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

2) Для данного k сравните сумму k + 1 смежных значений длин слотов. Таким образом, для k = 2, сравните сумму:

 { 4, 1, 0 }

 { 1, 0, 2 }

 { 0, 2, 4 }

3) Получить максимальное значение из суммы подмножеств. Максимальным значением будет длина допустимого смещения!

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

    int findBreakDuration(int n, int k, int start[], int end[], int t) {
     int max = Integer.MIN_VALUE;

         int initialTime = 0;
         List<Integer> freeSlots = new ArrayList<Integer>();

         for(int i =0;i<start.length;i++)
         {
             int startTime = start[i];
             int slot = startTime - initialTime;
             freeSlots.add(slot);
             initialTime = end[i];
         }
         freeSlots.add(t - end[end.length-1]);

         for(int i  =0 ; i< freeSlots.size()-k; i++)
         {
             int sum = 0;
             int m = i;
             for(int j=1;j<=k+1;j++)
             {
                 sum = sum + freeSlots.get(m);
                 m++;
             }
             System.out.println(sum);
             if(sum > max)
                 max = sum;
         }

        return max;
    }
}

Answer 4

Рабочий процесс действительно очень элегантный.

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) Победит последний, поэтому переместите эти презентации в любую сторону.