Maximum sum of the range non-overlapping intervals in a list of Intervals

Question

Someone asked me this question:
You are given a list of intervals. You have to design an algorithm to find the sequence of non-overlapping intervals so that the sum of the range of intervals is maximum.

For Example:
If given intervals are:

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

Range is maximized when three intervals

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

are chosen.

Therefore, the answer is 420 (minutes).

Convolve

Are you sure this is dynamic programming? – Confucianism

This is the classic weighted activity selection problem. – Mortgagor

Shouldnt your answer be 420 minutes? if those three are the selected intervals – Confucianism

Answer 1

This is a standard interval scheduling problem.
It can be solved by using dynamic programming.

Algorithm
Let there be n intervals. sum[i] stores maximum sum of interval up to interval i in sorted interval array. The algorithm is as follows

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])

The iteration goes for n steps and in each step, j can be found using binary search, i.e. in log n time. Hence algorithm takes O(n log n) time.

Photosphere

Yeah, I have implemented it a lot and I don't think its a very difficult one to understand. – Photosphere

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

    }


}

Heres the working code. Basically this runs in O(n^2) because of the two for loops. But as Shashwat said there are ways to make it run in O(n lg n)

Confucianism

Answer 3

You can implement it in O(nlogn) complexity, assuming that the start time, end time, and duration of the interval are i[0], i[1], and i[2], respectively, and you can implement it with this algorithm。

expl

The final selected intervals must be non-overlapping, and as a rule of thumb, the intervals are sorted by endTime.

Suppose we traverse each interval in the order it was sorted as above. We would like to think that if we chose the ith interval then we would have the opportunity to update such a record dp[endTime[i]], where dp[time] denotes the maximum gain up to the moment of time. Obviously, we would have dp[endTime[i]] = dp[startTime[i]] + profit[i].

Of course, we can't store the value of the maximum benefit at every moment in dp, we can only discretize it to store the maximum benefit at every endTime moment. That is, dp should be a hash table.

Thus, it is possible that there is no startTime[i] in the dp record, but we just need to find the last moment that is less than or equal to startTime[i], denoted as t, which corresponds to dp[t] = val.

In particular, note that our attempt to record dp[endTime[i]] = val + profit[i] presupposes that val + profit[i] must be greater than the last moment inside dp. That is, we only store time->profit key-value pairs inside the dp that are incremented by profit. In fact, it makes sense that if t0<t1 and dp[t0]>dp[t1], there's no need fort1 to be stuffed into the dp array (wasting time and decreasing returns).

Thus our algorithm comes to life. For the current interval i, we look inside the dp array (or ordered map) at the maximum gain val before the moment startTime[i], which we can get by binary search. Next, we have the opportunity to add dp[endTime[i]] = val+profit[i]. Note that there is another possibility if the optimal solution of dp[endTime[i]] is not to take the ith interval, in which case dp[endTime[i]] = dp[endTime[i-1]].

With such a sequence dp that is increasing in both time and gain, we can keep appending records of dp[endTime[i]] to create the maximum gain at the moment of update.

The implementation is as follows

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

Here are some relevant questions leetcode:1235. Maximum Profit in Job Scheduling

Bohrer