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 intervalsint 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 Codeint 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 approachimport 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 intervalsfrom queue import PriorityQueuedef 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 codeif __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
5
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
