Maximum Value of two non overlapping events

XXX. Maximum Value of Two Non-Overlapping Events

Priority Queue

Sorting

Greedy Algorithm

Problem Statement:

You are given a 2D array events, where each events[i] = [starti, endi, vali] represents an event that starts at time starti, ends at time endi, and has a value vali. You can attend at most two non-overlapping events.

Return the maximum sum of values of the two events you can attend. If you can only attend one event, return its value.

Algorithm:

1. Sort Events by Start Time:

   Sort the events array in ascending order of their start times. This ensures that we process events in chronological order.

2. Use a Priority Queue:

   Maintain a priority queue to store pairs of end time and value of the events that have been processed. The priority queue helps efficiently retrieve the event with the maximum value whose end time is less than the current event's start time.

3. Iterate Through Events:

   For each event:

   • Poll all events from the queue that end before the current event starts and update the maximum value seen so far.
   • Calculate the maximum sum by adding the current event's value to the maximum value of a non-overlapping event.
   • Add the current event to the priority queue.
4. Return the Maximum Sum:

   After processing all events, the maximum sum of values of two non-overlapping events is returned.

Complexity:

Time Complexity: O(n log n), where n is the number of events. Sorting the events takes O(n log n), and each priority queue operation takes O(log n).
Space Complexity: O(n), for the priority queue.

Java Implementation:

import javafx.util.Pair;
import java.util.*;

class Solution {
    public int maxTwoEvents(int[][] events) {
        // Create a PriorityQueue to store pairs of ending time and value.
        PriorityQueue> pq = new PriorityQueue<>(
            Comparator.comparingInt(Pair::getKey)
        );

        // Sort the array in ascending order by start time
        Arrays.sort(events, (a, b) -> a[0] - b[0]);

        int maxVal = 0, maxSum = 0;

        for (int[] event : events) {
            // Poll all valid events from the queue and take their maximum value.
            while (!pq.isEmpty() && pq.peek().getKey() < event[0]) {
                maxVal = Math.max(maxVal, pq.peek().getValue());
                pq.poll();
            }

            // Update the maximum sum with the current event's value
            maxSum = Math.max(maxSum, maxVal + event[2]);

            // Add the current event's end time and value to the priority queue
            pq.add(new Pair<>(event[1], event[2]));
        }

        return maxSum;
    }
}