LeetCode Entry

2054. Two Best Non-Overlapping Events

23.12.2025 medium 2025 kotlin rust

Max at most two non-overlapping events max

2054. Two Best Non-Overlapping Events medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1213

Problem TLDR

Max at most two non-overlapping events #medium #prefix_max #bs #pq

Intuition

    // ************
    // *****
    //  *****
    //   *****
    //    *****
    //     *****
    //     .*****
    //     . *****
    //
    // need a way to map[time][maxv]

• One way: sort by starts, put visited into PriorityQueue, poll by ends
• Another way: sort by ends, put visited into prefix-max list, binary search start in ends

Approach

• the prefix-max requires initial (0,0) value
• there is also a suffix-max solution

Complexity

• Time complexity: \(O(nlogn)\)

• Space complexity: \(O(n)\)

Code

// 135ms
    fun maxTwoEvents(e: Array<IntArray>): Int {
        var max = 0; val q = PriorityQueue<Int>(compareBy{e[it][1]})
        return e.indices.sortedBy { e[it][0]}.maxOf { i ->
            while (q.size > 0 && e[q.first()][1] < e[i][0])
                max = max(max, e[q.poll()][2])
            q += i; e[i][2] + max
        }
    }

// 10ms
    pub fn max_two_events(mut e: Vec<Vec<i32>>) -> i32 {
        let mut max = vec![(0,0)]; e.sort_unstable_by_key(|e|e[1]);
        e.iter().map(|e|{
            max.push((max[max.len()-1].0.max(e[2]), e[1]));
            e[2] + max[max.partition_point(|m| m.1 < e[0]) - 1].0
        }).max().unwrap()
    }