The Maximum Sum of Two Non-Overlapping Intervals in a List of Intervals | Interval Scheduling Problem

Optimal Approach

We will solve this problem to find the maximum sum of two non-overlapping intervals in a list of intervals | interval scheduling problem using a priority queue:

1. We will sort the array based on startTime if startTime is the same for two intervals, then we will sort the array on the basis of endTime.
2. We will store the pair {endTime, value} in the max heap (priority queue).
3. We will now traverse the array, and we will calculate the maximum value for all the intervals whose endTime is smaller than startTime, and we will store it in variable max.
4. Now, we will update ans after each traversal ans = max(ans, max + interval[i][2]).
5. Now we will return the final answer as ans.

Implementation in C++

// C++ code for Maximum sum of two non-overlapping intervals in a list of Intervals | Interval Scheduling Problem
#include <bits/stdc++.h>
using namespace std;


int maxTwoNonOverLapping(vector<vector<int> >& intervals)
{

    // sort the given array on the basis of startTime
    sort(intervals.begin(), intervals.end(),
        [](vector<int>& a, vector<int>& b) {
            return (a[0] == b[0]) ? a[1] < b[1]
                                : a[0] < b[0];
        });

    // to store the priority queue which
    // stores endTime and value of the interval
    // and sort on the basis of endTime
    priority_queue<vector<int> > pq;

    int maxx = 0;
    int ans = 0;

    for (auto x : intervals) {
        while (!pq.empty()) {

            // if endTime from priority queue is greater
            // than startTime of current interval then break
            if (pq.top()[0] >= x[0])
                break;
            vector<int> q = pq.top();
            pq.pop();

            // update the maxx variable
            maxx = max(maxx, q[1]);
        }

        // update the ans variable
        ans = max(ans, maxx + x[2]);
        pq.push({ x[1], x[2] });
    }

    // Returning ans
    return ans;
}

// Driver Code for the problem to find maximum sum of two non-overlapping intervals in a list of intervals | interval scheduling problem
int main()
{
    vector<vector<int> > intervals
        = { { 1, 3, 2 }, { 3, 5, 3 }, { 2, 4, 3 } };
    int maxValue = maxTwoNonOverLapping(intervals);
    cout << maxValue;

    return 0;
}

Output:

Input:  [[1, 3, 2], [3, 5, 3], [1, 4, 1] 
Output: 3

Complexity Analysis

Time Complexity:  O(N*logN)

Since we have sorted the array initially and sorting takes O(N*log(N)) time, therefore, the time complexity is O(N*log(N))

Space Complexity: O(N)

Since we are using a priority queue therefore the time complexity will be O(N).

Also check out - Inorder Predecessor

Frequently Asked Questions

What is a heap?

Heap is a tree-based data structure. More precisely, it is a particular case of a balanced binary tree that stores the tree’s nodes in a specific order.  

What is a priority queue?

The priority queue is similar to the regular queue. The only difference is that the priority queue stores elements in a particular order of priority where the top element has the highest priority.

What is a queue?

The queue is also a linear data structure, and it is based on the principle of FIFO (First in First Out)

Conclusion

This article discussed the maximum sum of two non-overlapping intervals in a list of Intervals | Interval Scheduling Problems. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

You can learn more about graphs here. Until then, Keep Learning and Keep Coding and practicing on Coding Ninjas Studio.

Recommended Reading:

• FCFS Scheduling
• Non Overlapping Intervals
• Maximum Number of Overlapping Intervals
• Heap and Priority Queue
• Understanding Heap Data Structure
• Top Array Coding Interview Questions

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!