2054.Two Best Non-Overlapping Events.md

Difficulty	Source	Tags
Medium	Daily Question (POTD 08-Dec)	Array Binary Search Dynamic Programming Sorting Heap (Priority Queue)

🎯 2054 - Two Best Non-Overlapping Events 🧠

Problem Link:

LeetCode - Two Best Non-Overlapping Events

💡 Problem Breakdown:

You are given a 2D array events, where each event is represented by three integers:

• startTimei: the starting time of the event,
• endTimei: the ending time of the event,
• valuei: the value of attending the event.

The task is to select at most two non-overlapping events such that the sum of their values is maximized.

• You cannot attend two events where one starts and the other ends at the same time.
• More formally, if you attend an event that ends at time t, the next event must start at t + 1 or later.

The problem asks to return the maximum sum of values of two non-overlapping events or the value of just one event if no two events can be selected.

🔍 Example Walkthrough:

Example 1:

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

Output:
4

Explanation:
You can attend event 0 (value = 2) and event 1 (value = 2), resulting in a sum of 4.

Example 2:

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

Output:
5

Explanation:
You can attend event 2 (value = 5) alone, resulting in the maximum value of 5.

Example 3:

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

Output:
8

Explanation:
You can attend event 0 (value = 3) and event 2 (value = 5), resulting in a sum of 8.

🎯 My Approach:

This problem can be efficiently solved using dynamic programming (DP) combined with sorting and binary search. The steps are as follows:

1. Sorting the Events:

   • First, sort the events by their end times. This allows us to consider events in the order they finish and helps in choosing non-overlapping events.

2. Dynamic Programming for Maximum Value:

   • We use a dynamic programming approach where dp[i] represents the maximum value we can get by selecting one event up to the i-th event.

3. Binary Search for Non-Overlapping Events:

   • To find the best event that can be paired with the current event, we need to search for the last event that ends before the current event starts. We can do this efficiently using binary search, since the events are sorted by their end time.

4. Maximizing the Result:

   • We calculate the maximum value by either selecting the current event alone or pairing it with a non-overlapping previous event.

🕒 Time Complexity:

• O(n log n): Sorting the events takes O(n log n), and for each event, we perform a binary search, which also takes O(log n). Hence, the overall complexity is dominated by the sorting and binary search operations.

• Space Complexity:
  O(n): We use an array dp[] to store the maximum values for each event, which requires space proportional to the number of events.

📝 Solution Code

Code (C):

int cmpEvents(const void *a, const void *b) {
    const int *eventA = *(const int **)a;
    const int *eventB = *(const int **)b;
    return eventA[0] - eventB[0];
}

int maxTwoEvents(int **events, int eventsSize, int *eventsColSize) {
    qsort(events, eventsSize, sizeof(events[0]), cmpEvents);

    int *suffixMax = (int *)malloc(eventsSize * sizeof(int));
    suffixMax[eventsSize - 1] = events[eventsSize - 1][2]; 

    for (int i = eventsSize - 2; i >= 0; --i) {
        suffixMax[i] = (events[i][2] > suffixMax[i + 1]) ? events[i][2] : suffixMax[i + 1];
    }

    int maxResult = 0;

    for (int i = 0; i < eventsSize; ++i) {
        int currentValue = events[i][2];
        int left = i + 1, right = eventsSize - 1;
        int end = events[i][1];

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (events[mid][0] > end) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left < eventsSize) {
            currentValue += suffixMax[left];
        }
        if (currentValue > maxResult) {
            maxResult = currentValue;
        }
    }

    free(suffixMax); 
    return maxResult;
}

Code (C++)

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        int n = events.size();
        vector<int> maxValues(n);
        maxValues[n - 1] = events[n - 1][2];

        for (int i = n - 2; i >= 0; --i) {
            maxValues[i] = max(maxValues[i + 1], events[i][2]);
        }

        vector<int> startTimes;
        for (const auto& event : events) {
            startTimes.push_back(event[0]);
        }

        int maxResult = 0;
        for (const auto& event : events) {
            int idx = upper_bound(startTimes.begin(), startTimes.end(), event[1]) - startTimes.begin();
            int value = event[2];
            if (idx < n) value += maxValues[idx];
            maxResult = max(maxResult, value);
        }

        return maxResult;
    }
};

Code (Java)

class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));

        int n = events.length;
        int[] maxValues = new int[n];
        maxValues[n - 1] = events[n - 1][2];
        for (int i = n - 2; i >= 0; --i) {
            maxValues[i] = Math.max(maxValues[i + 1], events[i][2]);
        }

        int maxResult = 0;
        for (int i = 0; i < n; ++i) {
            int nextIndex = binarySearch(events, events[i][1]);
            int currentValue = events[i][2];
            if (nextIndex < n) {
                currentValue += maxValues[nextIndex];
            }
            maxResult = Math.max(maxResult, currentValue);
        }

        return maxResult;
    }

    private int binarySearch(int[][] events, int target) {
        int low = 0, high = events.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (events[mid][0] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

Code (Python)

from bisect import bisect_right
from typing import List

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort()
        n = len(events)
        max_values = [0] * n
        max_values[-1] = events[-1][2]

        for i in range(n - 2, -1, -1):
            max_values[i] = max(max_values[i + 1], events[i][2])

        start_times = [event[0] for event in events]
        max_result = 0

        for start, end, value in events:
            idx = bisect_right(start_times, end)
            if idx < n:
                value += max_values[idx]
            max_result = max(max_result, value)

        return max_result

Code (Rust)

impl Solution {
    pub fn max_two_events(events: Vec<Vec<i32>>) -> i32 {
        let mut events = events;
        events.sort();

        let n = events.len();
        let mut max_values = vec![0; n];
        max_values[n - 1] = events[n - 1][2];

        for i in (0..n - 1).rev() {
            max_values[i] = max_values[i + 1].max(events[i][2]);
        }

        let mut max_result = 0;
        for i in 0..n {
            let value = events[i][2];
            let idx = events.binary_search_by(|event| event[0].cmp(&(events[i][1] + 1))).unwrap_or_else(|x| x);
            let total_value = if idx < n { value + max_values[idx] } else { value };
            max_result = max_result.max(total_value);
        }

        max_result
    }
}

🎯 Contribute or Ask Questions:

For more discussions, questions, or help with the solution, feel free to reach out on LinkedIn: Connect with Me!.

Enjoying the Solution?

If this helped you, please star this repo to support the efforts and keep it growing!