间隔列表中范围不重叠间隔的最大总和

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;
        }

    }


}

这是工作代码。基本上，由于有两个 for 循环，它的运行时间为 O(n^2)。但正如 Shashwat 所说，有一些方法可以让它在 O(n lg n) 中运行

Answer 3

你可以以

O(nlogn)

的复杂度来实现，假设开始时间、结束时间和间隔持续时间分别为

i[0]

、

i[1]

和

i[2]

，你可以用这个算法来实现。

解释

最终选择的间隔必须不重叠，并且根据经验，间隔按结束时间排序。

假设我们按照上面排序的顺序遍历每个区间。我们想，如果我们选择第 i 个间隔，那么我们将有机会更新这样的记录

dp[endTime[i]]

，其中

dp[time]

表示截至该时刻的最大增益。显然，我们会有

dp[endTime[i]] = dp[startTime[i]] + profit[i]

。

当然，我们不能将每个时刻的最大收益值存储在dp中，我们只能将其离散化，以存储每个endTime时刻的最大收益。也就是说，dp应该是一个哈希表。

因此，dp记录中可能没有

startTime[i]

，但我们只需要找到最后一个小于等于

startTime[i]

的时刻，记为t，对应于

dp[t] = val

。

特别注意，我们尝试记录

dp[endTime[i]] = val + profit[i]

的前提是

val + profit[i]

必须大于 dp 内的最后时刻。也就是说，我们只在 dp 中存储按利润递增的

 time->profit

键值对。事实上，如果

t0<t1

和

dp[t0]>dp[t1]

，就没有必要将

t1

塞到dp数组中（浪费时间，收益递减）。

我们的算法就这样诞生了。对于当前间隔 i，我们在 dp 数组（或有序映射）内部查看

startTime[i]

时刻之前的最大增益 val，我们可以通过

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。作业调度的最大利润