Two Best Non-Overlapping Events

Input

Number of events = 3

events = [[2, 5, 2], [3, 7, 3], [6, 9, 4]]

Output

Maximum number of points = 6

 

Explanation

We can attend the first and third events as they are non-overlapping. The total number of points, in this case, will be 2 + 4 = 6.

Note that if you attend the second event, you cannot attend any of the other two events as the second event clashes with each one of them.

 

Approach 1

A straightforward approach would be to consider all possible pairs of events. If a pair of events is non-overlapping, update the answer with answer = max(answer, sum of points of these two events). 

 

Algorithm

1. Create a function check_collision which takes two events, A and B, as parameters. If startTimeA <= endTimeB and startTimeB <= endTimeA then the two events clash, otherwise not. This condition checks if each of the events starts before the other one ends.
2. Iterate the array of events and let i be the index of the current event.
3. For all events with index j > i, check if it clashes with the current event using the function check_collision.
4. If they don't clash, update the answer with answer = max(answer, sum of points of these two events)

 

Program

#include<bits/stdc++.h> using namespace std; bool check_collision(vector<int>& eventA, vector<int>& eventB){ // function to check collision between two events.     int startTimeA = eventA[0], endTimeA = eventA[1];     int startTimeB = eventB[0], endTimeB = eventB[1];     if(startTimeA <= endTimeB && startTimeB <= endTimeA){ // to check if each of the events starts before the other ends.         return true;     }     return false; } int main(){     int n; cin>>n;     vector<vector<int>> events(n, vector<int>(3));     for(int i=0;i<n;i++){         cin>>events[i][0]>>events[i][1]>>events[i][2];     }     int ans=0;     for(int i = 0; i < n; i++){         ans = max(ans, events[i][2]); // consider the condition when you can attend only one event.         for(int j = i + 1; j < n; j++){             if(check_collision(events[i], events[j])){                 continue; // if they collide then continue.             }             else ans=max(ans, events[i][2] + events[j][2]); // otherwise update the answer.         }     }     cout<<ans<<endl; }

 

Input

Number of events = 3

events = [[2, 5, 2], [3, 7, 3], [6, 9, 4]]

 

Output

Maximum number of points = 6

 

Time Complexity

The time complexity of the above algorithm is O(n^2), as we are using two nested loops in the approach.

 

Space Complexity

The space complexity of the above algorithm is O(1), as we are not using any extra memory during runtime.

Read More - Time Complexity of Sorting Algorithms

Approach 2

This approach uses binary search to solve the problem. Let us sort the events array based on the start times of events. Create an array suffix_max_point_event of size N. Update the array such that for each index i, suffix_max_point_event[i] holds the maximum number of points among events with index >= i.

Now, for each event in this array, find the maximum valued event which starts after this event ends. Using binary search, we can find the number of points of such an event in O(log N) time.

 

Algorithm

1. Sort the array of events.
2. Create an array suffix_max_point_array of size N. Initialize suffix_max_point_array[N - 1] = events[N - 1][2]. 
3. Iterate i from N - 2 to 0 and update suffix_max_point_array[i] = max(suffix_max_point_array[i+1], events[i][2]). This ensures that suffix_max_point_array[i] holds the maximum number of points among all events with index >= i.
4. Iterate the events array and let i be the index of the current event.
5. Do a binary search in the events array to find the index of the first event in the events array, which starts after the current event ends.
6. Create a vector next_event = {events[i][1] + 1, -1, -1}. Any vector in the events array which is greater than next_event must start after the current event.
7. Let ind be the index of the first event in the events array satisfying the condition. Then all the events with index >= ind start after the current event (as the events array is sorted).
8. Update the answer with answer = max(answer, events[i][2] + suffix_max_point_array[ind]). As suffix_max_point_array holds the maximum number of points among all events with index >= ind.

 

Program

#include<bits/stdc++.h> using namespace std; int main(){     int n; cin>>n;     vector<vector<int>> events(n, vector<int>(3));     for(int i=0;i<n;i++){         cin>>events[i][0]>>events[i][1]>>events[i][2];     }     sort(events.begin(), events.end()); // sort the events array using sort function.     int ans = 0; // the final answer initialized with 0.     vector<int> suffix_max_point_event(n);      suffix_max_point_event[n-1]=events[n-1][2]; // update the last index with the points of the last event in the sorted array.     for(int i=n-2;i>=0;i--){         suffix_max_point_event[i]=max(suffix_max_point_event[i+1],events[i][2]); // suffix_max_point_event[i] holds the maximum valued event with index >= i.     }     for(int i=0;i<n;i++){         // This event ends at events[i][1].         // binary search to find the starting index of such an event which starts after this event ends.         vector<int> next_event={events[i][1]+1, -1,-1};         auto it=lower_bound(events.begin(),events.end(),next_event);         // lower_bound function returns the first event in the events array which is greater than or equal to the next_event.                  if(it==events.end()){ // there is no such event which starts after this event ends.             ans=max(ans,events[i][2]); // we can attend one event as well.             continue;         }         int ind=it-events.begin(); // All the events with index >= ind start after this event ends.         int curr_ans = events[i][2]+suffix_max_point_event[ind];  // Choose this event and the maximum valued event with index >= i.  //Our suffix_max_point_event holds the number of points of such an event.         ans=max(ans,curr_ans); // update the answer.     }     cout<<ans<<endl; }

Input

Number of events = 3

events = [[2, 5, 2], [3, 7, 3], [6, 9, 4]]

 

Output

Maximum number of points = 6

 

Time Complexity

The time complexity of the above algorithm is O(N * log(N)). It is because, the sort function has the time complexity of O(N * log(N)).

Furthermore, for each event in the array, the algorithm calls the lower_bound function, which has O(log(n)) time complexity (typical binary search time complexity). So the total time complexity becomes O( N * log(N)).

 

Space Complexity

The space complexity of the above algorithm is the same as that of the previous algorithm, O(1), as we are not using any extra memory during runtime.

 

Approach 3

We can also solve the problem using a tricky construction. This type of construction is often used to solve problems based on intervals. So, it is highly recommended that you remember these kinds of approaches. 

Create two 2-dimensional vectors - startTimes and endTimes. For each event in the array, push the start time and value into startTimes and the end time and value into endTimes. Sort the two vectors. Now iterate the startTimes vector and update the answer with answer = max(answer, points of the current event + maximum points of the events ended so far).

 

Algorithm

1. Create two vectors, startTimes and endTimes, and populate them according to the procedure described in the approach above.
2. Sort the vectors - startTimes and endTimes.
3. Maintain a variable max_point_ended_event that keeps track of the maximum valued event that has ended so far and index j to iterate in the endTimes vector.
4. Iterate the startTimes vector and while endTimes[j][0] is less than startTimes[i][0], update max_point_ended_event with max(max_point_ended_event, endTimes[j][1]) and increment j.
5. endTimes[j][0] < startTimes[i][0] implies that the event with endTimes[j][0] has already ended, hence its points can be taken into account.
6. Update the answer with max(answer, startTimes[j][1] + max_point_ended_event).

Program

#include<bits/stdc++.h> using namespace std; int main(){     int n; cin>>n;     vector<vector<int>> events(n, vector<int>(3));     for(int i=0;i<n;i++){         cin>>events[i][0]>>events[i][1]>>events[i][2];     }     int n=events.size();     int ans=0;     vector<vector<int>> startTimes, endTimes; // create the vectors.     for(int i=0;i<n;i++) {         startTimes.push_back({events[i][0], events[i][2]}); // push the start time and value to startTimes.         endTimes.push_back({events[i][1], events[i][2]}); // push the end time and value to endTimes.     }     sort(startTimes.begin(), startTimes.end()); // sort the vectors.     sort(endTimes.begin(), endTimes.end());     int j=0; // index to keep track of the current event in the endTimes vector.     int max_point_ended_event = 0; // variable that stores maximum number of points among events ended so far.     for(int i = 0; i < n; i++){         // iterate the endTimes vector to find events which ended before this event.         while(j < n && endTimes[j][0] < startTimes[i][0]){             max_point_ended_event = max(max_point_ended_event, endTimes[j][1]); // update the max_point_ended_event variable to contain the maximum number of points.             j++;         }         // update the answer with ans = max(ans, points of the current event + maximum points of the events ended so far).         ans = max(ans, startTimes[i][1] + max_point_ended_event);     }     return ans; }

 

Input

Number of events = 3

events = [[2, 5, 2], [3, 7, 3], [6, 9, 4]]

 

Output

Maximum number of points = 6

 

Time Complexity

The time complexity of the above algorithm is O(N * log(N)). It is because, the sort function has the time complexity of O(N * log(N)). However, the for loops contribute O(N) time complexity.

Space Complexity

The space complexity of the above algorithm is O(N). It is because we are creating two arrays of sizes of the order of O(N).

Key Takeaways

This blog aimed to solve the coding using various approaches. The first one used brute force to solve the problem. This algorithm will most probably lead to TLE.

The second approach uses binary search to solve the problem. We can also use the upper_bound function (defined in C++ STL) to do a binary search with minor changes in the next_event vector.

The third approach uses a trick to get to the solution. This trick is widely used to solve problems based on intervals.

Check out this problem - Two Sum Problem

Yet learning never stops, and there is a lot more to learn.

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!