The maximum sum of two non-overlapping intervals in a list of Intervals | Interval Scheduling Problem

Vibhor Bhatnagar
Last Updated: May 13, 2022

Introduction 

The problem is the maximum sum of two non-overlapping intervals in a list of Intervals | Interval Scheduling Problem, and we are given an array of length N, where each element has three values, i.e. {startTime, endTime, value}. Our task is to find the maximum sum of values of two non-overlapping intervals. 

So before we deep dive into the solution to this problem, we should first look at some examples to understand the problem better.

Sample Examples

Input: intervals[]= [[1, 2, 3], [3, 5, 5], [1, 4, 5]]

Output: 8

We will select intervals 1 and 2 since they are non-overlapping (the third interval is overlapping). So, the maximum sum will be 3+5 = 8. 

Input:  intervals[]= [[1, 3, 6], [3, 5, 5], [2, 6, 5]] 

Output: 6

We will select interval one since the other two are overlapping intervals, and their maximum value is 5, which is less than the first interval value. So, the maximum sum would be 6.

Brute Force Approach

  1. We will sort the intervals[] array given to us.
  2. After that, we will check for each interval if another interval does not overlap with the current interval. If we find any such interval, we will take the sum of values of the two intervals.
  3. We will store the sum of the intervals in a variable, and we will take the maximum of the answer and this variable over all the n intervals.
  4. After that, we will return the answer.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

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

    int ans = 0;
    sort(intervals.begin(), intervals.end());
    for (int i = 0; i < intervals.size(); i++)
    {
        int curr = 0;
        for (int j = i + 1; j < intervals.size(); j++)
        {
            if (intervals[j][0] > intervals[i][1])
            {
                curr = intervals[j][2] + intervals[i][2];
            }
            ans = max(ans, curr);
        }
    }
    // 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 = {{3, 3, 2}, {4, 5, 3}, {2, 4, 3}};
    int maxValue = maxTwoNonOverLapping(intervals);
    cout << maxValue;

    return 0;
}

 

Output:

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

 

Complexity Analysis

Time Complexity:  O(N*N)

The time complexity of the above approach is O(N*N) because we are using two nested loops.

Space Complexity: O(1)

Since we are not using any extra array to store the answer, therefore, the space complexity will be O(1). 

Optimal Approach

We will solve this problem to find 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).

Frequently asked questions

Q1. What is a heap?

Ans. 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. 
 

Q2. What is a priority queue?

Ans. 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.

 

Q3. What is a queue?

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

Key takeaways

This article discussed the maximum sum of two non-overlapping intervals in a list of Intervals | Interval Scheduling Problem. 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 hereUntil then, Keep Learning and Keep Coding and practicing on Code studio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think