Hello and welcome back brave human being!

Before we delve into the problem, I just want to confess that this last problem almost broke me 😭. I’ve been Leetcoding on and off for more than 3 years and I still find it difficult.

If you struggled with the last problem, I did too.

Now that I understand the solution, I will do my best to break it down so you can easily understand it.

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

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.

Let's set an 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.

The naive solution for this problem would be to iterate the array with a double for loop, find the non-overlapping intervals, and find the maximum value with each iteration.

The naive solution would have a big O Notation of O(N² ), which would be quite slow, so let’s start making some optimizations.

The first thing would be to….. sort! Since we have three values in each element, we want to sort them by start time, If two events have the same start time, they are sorted based on their end times. By sorting the array, we ensure that we process events chronologically, essential for efficiently identifying non-overlapping events.

sort(events.begin(), events.end(),
     [](vector<int>& a, vector<int>& b) {
         return (a[0] == b[0]) ? a[1] < b[1] : a[0] < b[0];
     });

The idea is to sort the intervals and for each interval, we find its best match between the already processed intervals.

Imagine we are currently at interval k, and to the far left of interval_k there are 100 hundred sets that may overlap, but none of them overlap with interval_k we are currently processing. It's simple to see that to find the best match for interval_k within those 100 intervals, the answer is the interval with the highest value (remember we established none of the 100 intervals overlap with interval_k).

Remember that we sorted the intervals in the very beginning.

Let's say that for interval_k, its best match was match_k (found in those 100 intervals to the far left).

Because the intervals were sorted, match_k is a potential match for every interval to the right of interval_k. We say potential because maybe something better comes up. Maybe interval_k+1 finds a match with a higher value with interval_k.

So now interval_k needs to be added to the list of processed intervals (making it 101).

And now we repeat all the above processes for interval_k+1.

When processing interval_k, we want to keep the relevant information, to find its potential match.

Let’s think about what is relevant to store….

We have the Start and End Time and its value for each interval.

Think about what would be relevant to determine if interval_k+1 overlaps with interval_k. Since we can guarantee interval_k has an earlier start time (we've already sorted them), we would only need to check if interval_k's end time occurs before interval_k+1's start time. Therefore, we can store interval_k's end time to compare it with interval_k+1's start time.

What else would be useful to store from interval_k?

Its value! 🤑 

Since we aim to determine if interval_k is our potential match based on the sum of values.

Therefore, we have determined to store a processed interval’s end time and value.

How can we store the end time and value of each processed interval?

We'll use a priority queue sorted in increasing order to maintain the order of intervals and prioritize the interval with the earliest end time.

Inside our for loop we’ll have a variable best_match, in where we will store the maximum value fo

Now that we have determined the relevant information for each processed interval, let's discuss how we iterate through the sorted list of intervals using a for loop.

1. For each event, iterate through the priority queue.

2. Check if it doesn’t overlap with the current interval by comparing the start time of the current event with the end time of the top of the queue.

3. If it doesn’t overlap, update the best_match variable to store the maximum value encountered so far.

4. Pop the top of the queue.

5. If it does overlap, skip the interval.

6. Once done comparing the current interval with the processed intervals, update the ans variable with the maximum sum of non-overlapping events.

7. Push the interval's end time and value onto the priority queue.

Once we are done processing all intervals, return the ans variable.

Let’s continue with a visual example:

The purple indicates current intervals, green indicates past intervals.

Complete solution:

Max Two Events

        #include <vector>
        #include <queue>
        #include <algorithm>

        using namespace std;

        class Solution {
        public:
            int maxTwoEvents(vector<vector<int>>& events) {
                sort(events.begin(), events.end(),
                     [](vector<int>& a, vector<int>& b) {
                         return (a[0] == b[0]) ? a[1] < b[1] : a[0] < b[0];
                     });
                priority_queue<vector<int> > pq;

                // Initializing max
                // and ans variables
                int ma = 0;
                int ans = 0;

                // Traversing the given array
                for (auto e : events) {
                    while (!pq.empty()) {
                        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] });
                }

                return ans;
            }
        };
    

This solution will result in an O(N Log N) Time Complexity! Quite the optimization from our naive solution!

This problem has a lot of moving pieces and I’ve made the best effort

Cheers to finally tackling this problem!!!!!

See you tomorrow!!!

Denisse