Maximum sum of at most two non-overlapping intervals in a list of Intervals | Interval Scheduling Problem

0 0 5 minutes read

Given an array interval of length N, where each element represents three values, i.e. {startTime, endTime, value}. The task is to find the maximum sum of values of at most two non-overlapping intervals.

Example:

Input: interval[] = [[1, 3, 2], [4, 5, 2], [2, 4, 3]]Output: 4
Explanation: Select interval 1 and 2 (as third interval is overlapping). Therefore, maximum value is 2 + 2 = 4.

Input: interval[] = [[1, 3, 2], [4, 5, 2], [1, 5, 5]]Output: 5
Explanation: As intervals 1 and 2 are non-overlapping but their value will be 2 + 2 = 4. So, instead of 1 and 2, only 3 can be selected with a value of 5.

Approach: This problem can be solved with the help of a priority queue. To solve this problem, follow the below steps:

Sort the given array interval w.r.t. startTime. If startTime of two intervals are the same then sort it on the basis of endTime.
Store the pair of {endTime, value} in the priority queue and sort on the basis of endTime.
Traverse the given array and calculate the maximum value for all events whose endTime is smaller than the startTime of the present interval and store it in variable max.
Now, update the ans, after each traversal as, ans= Math.max(ans, max + interval[i][2]).
Return ans as the final answer to this problem.

Below is the implementation of the above approach

C++

// C++ algorithm for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// maximum value of atmost two
// non-overlapping intervals
int maxTwoNonOverLapping(vector<vector<int> >& interval)
{
   
    // Sorting the given array
    // on the basis of startTime
    sort(interval.begin(), interval.end(),
         [](vector<int>& a, vector<int>& b) {
             return (a[0] == b[0]) ? a[1] < b[1]
                                   : a[0] < b[0];
         });
 
    // Initializing Priority Queue
    // which stores endTime
    // and value and sort
    // on the basis of endTime
    priority_queue<vector<int> > pq;
   
    // Initializing max
    // and ans variables
    int ma = 0;
    int ans = 0;
 
    // Traversing the given array
    for (auto e : interval) {
        while (!pq.empty()) {
 
            // If endTime from priority
            // queue is greater
            // than startTime of
            // traversing interval
            // then break the loop
            if (pq.top()[0] >= e[0])
                break;
            vector<int> qu = pq.top();
            pq.pop();
 
            // Updating max variable
            ma = max(ma, qu[1]);
        }
 
        // Updating ans variable
        ans = max(ans, ma + e[2]);
        pq.push({ e[1], e[2] });
    }
 
    // Returning ans
    return ans;
}
 
// Driver Code
int main()
{
    vector<vector<int> > interval
        = { { 1, 3, 2 }, { 4, 5, 2 }, { 1, 5, 5 } };
    int maxValue = maxTwoNonOverLapping(interval);
    cout << maxValue;
 
    return 0;
}
 
    // This code is contributed by rakeshsahni

Java

// Java algorithm for above approach
 
import java.util.*;
 
class GFG {
 
    // Driver Code
    public static void main(String[] args)
    {
        int[][] interval
            = { { 1, 3, 2 }, { 4, 5, 2 }, { 1, 5, 5 } };
        int maxValue = maxTwoNonOverLapping(interval);
        System.out.println(maxValue);
    }
 
    // Function to find
    // maximum value of atmost two
    // non-overlapping intervals
    public static int maxTwoNonOverLapping(int[][] interval)
    {
        // Sorting the given array
        // on the basis of startTime
        Arrays.sort(interval,
                    (a, b)
                        -> (a[0] == b[0]) ? a[1] - b[1]
                                          : a[0] - b[0]);
 
        // Initializing Priority Queue
        // which stores endTime
        // and value and sort
        // on the basis of endTime
        PriorityQueue<int[]> pq
            = new PriorityQueue<>((a, b) -> a[0] - b[0]);
 
        // Initializing max
        // and ans variables
        int max = 0;
        int ans = 0;
 
        // Traversing the given array
        for (int[] e : interval) {
            while (!pq.isEmpty()) {
 
                // If endTime from priority
                // queue is greater
                // than startTime of
                // traversing interval
                // then break the loop
                if (pq.peek()[0] >= e[0])
                    break;
                int[] qu = pq.remove();
 
                // Updating max variable
                max = Math.max(max, qu[1]);
            }
 
            // Updating ans variable
            ans = Math.max(ans, max + e[2]);
            pq.add(new int[] { e[1], e[2] });
        }
 
        // Returning ans
        return ans;
    }
}

Python3

## Python program for the above approach:
 
## Function to find
## maximum value of atmost two
## non-overlapping intervals
from queue import PriorityQueue
 
def maxTwoNonOverLapping(interval):
    ## Sorting the given array
    ## on the basis of startTime
    interval.sort()
 
    ## Initializing Priority Queue
    ## which stores endTime
    ## and value and sort
    ## on the basis of endTime
    pq = PriorityQueue()
 
    ## Initializing max
    ## and ans variables
    ma = 0;
    ans = 0
 
    ## Traversing the given array
    for e in interval:
        while not pq.empty():
 
            ## If endTime from priority
            ## queue is greater
            ## than startTime of
            ## traversing interval
            ## then break the loop
            if (pq.queue[0][0] >= e[0]):
                break;
            qu = pq.get();
 
            ## Updating max variable
            ma = max(ma, qu[1]);
 
        ## Updating ans variable
        ans = max(ans, ma + e[2]);
        pq.put([ e[1], e[2] ]);
 
    ## Returning ans
    return ans;
 
## Driver code
if __name__=='__main__':
 
    interval = [ [ 1, 3, 2 ], [ 4, 5, 2 ], [ 1, 5, 5 ] ];
     
    maxValue = maxTwoNonOverLapping(interval);
    print(maxValue);
 
    # This code is contributed by subhamgoyal2014.

C#

using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
  // Driver Code
  public static void Main(string[] args)
  {
    int[][] interval = new int[][] {
      new int[] { 1, 3, 2 },
      new int[] { 4, 5, 2 },
      new int[] { 1, 5, 5 }
    };
    int maxValue = maxTwoNonOverLapping(interval);
    Console.WriteLine(maxValue);
  }
 
  // Function to find maximum value of atmost two non-overlapping intervals
  public static int maxTwoNonOverLapping(int[][] interval)
  {
    // Sorting the given array on the basis of startTime
    var sorted = interval.OrderBy(a => a[0]).ThenBy(a => a[1]);
    interval = sorted.ToArray();
 
    // Initializing SortedSet which stores endTime and value
    SortedSet<int[]> pq = new SortedSet<int[]>(Comparer<int[]>.Create((a, b) => a[0].CompareTo(b[0])));
 
    // Initializing max and ans variables
    int max = 0;
    int ans = 0;
 
    // Traversing the given array
    foreach (int[] e in interval) {
      while (pq.Count > 0) {
 
        // If endTime from priority queue is greater
        // than startTime of traversing interval then break the loop
        if (pq.First()[0] >= e[0])
          break;
        int[] qu = pq.First();
        pq.Remove(qu);
         
        // Updating max variable
        max = Math.Max(max, qu[1]);
      }
 
      // Updating ans variable
      ans = Math.Max(ans, max + e[2]);
      pq.Add(new int[] { e[1], e[2] });
    }
 
    // Returning ans
    return ans;
  }
 
}
 
// This code is contributed by phasing17.

Javascript

<script>
    // Javascript program for the above approach:
     
    // Function to find
    // maximum value of atmost two
    // non-overlapping intervals
     
    function maxTwoNonOverLapping(interval){
        // Sorting the given array
        // on the basis of startTime
        interval.sort();
     
        // Initializing Priority Queue
        // which stores endTime
        // and value and sort
        // on the basis of endTime
        pq = [];
     
        // Initializing max
        // and ans variables
        ma = 0;
        ans = 0
     
        // Traversing the given array
        for(let i=0;i<interval.length;i++){
            e=interval[i];
            while(pq.length){
     
                // If endTime from priority
                // queue is greater
                // than startTime of
                // traversing interval
                // then break the loop
                if (pq[0][0] >= e[0]){
                    break;
                }
                qu = pq[0];
                pq.pop(0);
     
                // Updating max variable
                ma = Math.max(ma, qu[1]);
            }
            // Updating ans variable
            ans = Math.max(ans, ma + e[2]);
            pq.push([ e[1], e[2] ]);
            pq.sort();
        }
     
        // Returning ans
        return ans;
    }
        // Driver code
     
        let interval = [ [ 1, 3, 2 ], [ 4, 5, 2 ], [ 1, 5, 5 ] ];
         
        let maxValue = maxTwoNonOverLapping(interval);
        document.write(maxValue);
     
        // This code is contributed by Aman Kumar.
     
</script>

Output

Time Complexity: O(NlogN)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!