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

Also see, Data Structures

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

**Recommended:** Try the Problem yourself before moving on to the solution.

## Brute Force Approach

- We will sort the intervals[] array given to us.
- 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 the values of the two intervals.
- 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.
- 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).

Also read, __Euclid GCD Algorithm__