Максимальная сумма интервалов неперекрывающихся интервалов в списке интервалов

Question

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

Например:
Если заданы интервалы:

["06:00","08:30"],
["09:00","11:00"],
["08:00","09:00"],
["09:00","11:30"],
["10:30","14:00"],
["12:00","14:00"]

Диапазон максимальный, когда три интервала

[“06:00”, “08:30”],
[“09:00”, “11:30”],
[“12:00”, “14:00”],

выбраны.

Поэтому ответ 420 (минут).

Answer 1

Это стандартная проблема планирования интервалов.
Это можно решить с помощью динамического программирования.

Алгоритм
Пусть будет n интервалы. sum[i] сохраняет максимальную сумму от интервала до интервала i в отсортированном интервале массива. Алгоритм заключается в следующем

Sort the intervals in order of their end timings.
sum[0] = 0
For interval i from 1 to n in sorted array
    j = interval in 1 to i-1 whose endtime is less than beginning time of interval i.
    If j exist, then sum[i] = max(sum[j]+duration[i],sum[i-1])
    else sum[i] = max(duration[i],sum[i-1])

Итерация идет для n шаги и на каждом этапе, j можно найти с помощью бинарного поиска, то есть в log n время. Следовательно, алгоритм принимает O(n log n) время.

Answer 2

public int longestNonOverLappingTI(TimeInterval[] tis){
        Arrays.sort(tis);
        int[] mt = new int[tis.length];
        mt[0] = tis[0].getTime();
        for(int j=1;j<tis.length;j++){
            for(int i=0;i<j;i++){
                int x = tis[j].overlaps(tis[i])?tis[j].getTime():mt[i] + tis[j].getTime();
                mt[j]  = Math.max(x,mt[j]);
            }
        }

        return getMax(mt);
    }


public class TimeInterval implements Comparable <TimeInterval> {
    public int start;
    public int end;
    public TimeInterval(int start,int end){
        this.start = start;
        this.end = end;

    }



    public boolean overlaps(TimeInterval that){
          return !(that.end < this.start || this.end < that.start);
    }

    public int getTime(){
        return end - start;
    }
    @Override
    public int compareTo(TimeInterval timeInterval) {
        if(this.end < timeInterval.end)
            return -1;
        else if( this.end > timeInterval.end)
            return 1;
        else{
            //end timeIntervals are same
            if(this.start < timeInterval.start)
                return -1;
            else if(this.start > timeInterval.start)
                return 1;
            else
                return 0;
        }

    }


}

Вот рабочий код. В основном это работает в O(n^2) из-за двух циклов for. Но, как сказал Шашват, есть способы заставить его работать в O(n lg n)

Answer 3

Вы можете реализовать это вO(nlogn)сложность, предполагая, что время начала, время окончания и продолжительность интервалаi[0],i[1], иi[2]соответственно, и вы можете реализовать это с помощью этого алгоритма。

объяснить

Окончательно выбранные интервалы не должны перекрываться, и, как правило, интервалы сортируются по endTime.

Предположим, мы проходим каждый интервал в том порядке, в котором он был отсортирован, как указано выше. Нам хотелось бы думать, что если бы мы выбрали i-й интервал, то у нас была бы возможность обновить такую ​​запись, гдеdp[time]обозначает максимальный выигрыш на данный момент времени. Очевидно, мы имели быdp[endTime[i]] = dp[startTime[i]] + profit[i].

Конечно, мы не можем хранить значение максимальной выгоды в каждый момент времени в dp, мы можем только дискретизировать ее, чтобы сохранить максимальную выгоду в каждый момент времени endTime. То есть dp должна быть хеш-таблицей.

Таким образом, возможно, что в записи dp ее нет, а нам просто нужно найти последний момент, который меньше или равен , обозначаемый как t, что соответствуетdp[t] = val.

В частности, отметим, что наша попытка записатьdp[endTime[i]] = val + profit[i]предполагает, чтоval + profit[i]должно быть больше, чем последний момент внутри dp. То есть мы храним только time->profitпары ключ-значение внутри dp, которые увеличиваются за счет прибыли. На самом деле имеет смысл, еслиt0<t1иdp[t0]>dp[t1], в этом нет необходимостиt1для заполнения в массиве dp (трата времени и уменьшение отдачи).

Таким образом наш алгоритм оживает. Для текущего интервала i мы смотрим внутри массива dp (или упорядоченной карты) на максимальное значение усиления до моментаstartTime[i], с помощью которого мы можем пройтиbinary search. Далее у нас есть возможность добавитьdp[endTime[i]] = val+profit[i]. Обратите внимание, что существует еще одна возможность, если оптимальное решение dp[endTime[i]] состоит в том, чтобы не брать i-й интервал, и в этом случаеdp[endTime[i]] = dp[endTime[i-1]].

С такой последовательностью dp, которая увеличивается как по времени, так и по усилению, мы можем продолжать добавлять записиdp[endTime[i]]создать максимальный прирост на момент обновления.

Реализация следующая

      
class Solution {
  static bool cmp(vector<int>& a, vector<int>& b)
  {
    return a[1] < b[1];
  }
public:
  int jobScheduling(vector<int>& s, vector<int>& e, vector<int>& v)
  {
    int n = s.size();
    vector<vector<int>>jobs;
    for (int i = 0; i < n; i++) jobs.push_back({ s[i],e[i],v[i] });
    sort(jobs.begin(), jobs.end(), cmp);
    map<int, int>dp;
    dp[-1] = 0;
    int ret = 0;
    for (int i = 0; i < n; i++)
    {
      int ans = ret;
      auto iter = dp.upper_bound(jobs[i][0]);
      ans = max(ans, prev(iter, 1)->second + jobs[i][2]);
      dp[jobs[i][1]] = ans;
      ret = max(ret, ans);
    }
    return ret;
  }
};

Вот несколько соответствующих вопросов . Leetcode:1235. Максимальная прибыль от планирования заданий