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

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

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

["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 (минут).


algorithm intervals dynamic-programming greedy
person Black_Hat    schedule 15.08.2013    source источник
comment
Вы уверены, что это динамическое программирование?   -  person smk    schedule 16.08.2013
comment
Это классическая задача выбора взвешенной активности.   -  person digital_revenant    schedule 16.08.2013
comment
Разве ваш ответ не должен быть 420 минут? если эти три являются выбранными интервалами   -  person smk    schedule 21.08.2013

Ответы (2)


arrow_upward
9
arrow_downward

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

Алгоритм
Пусть будет 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) времени.

person Shashwat Kumar    schedule 15.08.2013
comment
Да, я реализовал это много, и я не думаю, что это очень сложно понять. - person Shashwat Kumar; 16.08.2013

arrow_upward
2
arrow_downward 

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)

person smk    schedule 15.08.2013