Two Best Non-Overlapping Events - Practice Coding Problems

Two Best Non-Overlapping Events - Problem

Array Binary Search Dynamic Programming Sorting Heap (Priority Queue) Medium

You are given a 0-indexed 2D integer array of events where events[i] = [startTime_i, endTime_i, value_i]. The i^th event starts at startTime_i and ends at endTime_i, and if you attend this event, you will receive a value of value_i.

You can choose at most two non-overlapping events to attend such that the sum of their values is maximized.

Return this maximum sum.

Note: The start time and end time is inclusive. You cannot attend two events where one starts and the other ends at the same time. If you attend an event with end time t, the next event must start at or after t + 1.

Input & Output

Example 1 — Basic Case

$ Input: events = [[1,3,2],[4,5,2],[2,4,3],[1,5,5]]

› Output: 5

💡 Note: We can choose events [1,5,5] alone for value 5, or [1,3,2] and [4,5,2] for value 4. The maximum is 5.

Example 2 — Two Non-overlapping

$ Input: events = [[1,3,2],[4,5,2],[1,5,5]]

› Output: 5

💡 Note: Either choose [1,5,5] alone for value 5, or [1,3,2] and [4,5,2] for value 4. Maximum is 5.

Example 3 — Clear Two Best

$ Input: events = [[1,5,3],[1,5,1],[6,6,5]]

› Output: 8

💡 Note: Choose [1,5,3] and [6,6,5] since they don't overlap: 3 + 5 = 8.

Constraints

2 ≤ events.length ≤ 10⁵
events[i].length == 3
1 ≤ start_i ≤ end_i ≤ 10⁹
1 ≤ value_i ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Events

List of events with start time, end time, and value

Find Compatible

Identify which events can be paired without overlap

Maximize Sum

Choose best single event or pair that gives maximum total value

Key Takeaway

🎯 Key Insight: Sort events by end time and use binary search to efficiently find compatible event pairs

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to sort events by end time and use binary search to efficiently find non-overlapping events. Best approach uses sorting + binary search + DP for O(n log n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all possible pairs of events to find maximum sum
Sort and Binary Search	O(n log n)	O(n)	Sort events by end time and use binary search to find compatible events

Brute Force — Algorithm Steps

Try each event as first choice
For each first event, try all other events as second choice
Check if events don't overlap (end1 < start2 or end2 < start1)
Track maximum sum and single event maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Events

List all events with their time ranges and values

Check Pairs

For each pair, verify if they don't overlap

Track Maximum

Keep track of the best sum found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int events[][3], int n) {
    int maxSum = 0;
    
    // Try single events
    for (int i = 0; i < n; i++) {
        if (events[i][2] > maxSum) {
            maxSum = events[i][2];
        }
    }
    
    // Try all pairs
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int start1 = events[i][0], end1 = events[i][1], val1 = events[i][2];
            int start2 = events[j][0], end2 = events[j][1], val2 = events[j][2];
            
            // Check if non-overlapping
            if (end1 < start2 || end2 < start1) {
                int sum = val1 + val2;
                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small inputs
    int events[100][3];
    int n = 0;
    
    char *ptr = strchr(line, '[');
    while (ptr && n < 100) {
        ptr = strchr(ptr, '[');
        if (!ptr) break;
        ptr++;
        
        sscanf(ptr, "%d,%d,%d", &events[n][0], &events[n][1], &events[n][2]);
        n++;
        
        ptr = strchr(ptr, ']');
        if (ptr) ptr++;
    }
    
    printf("%d\n", solution(events, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all pairs of events

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum values

✓ Linear Space

78.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler