Kotlin | Rust
\n\nhttps://youtu.be/uBoGo4P9t9E\n\n#### Join me on Telegram\n\nhttps://t.me/leetcode_daily_unstoppable/826\n\n#### Problem TLDR\n\nMax two non-overlapping inte
![1.webp](https://assets.leetcode.com/users/images/ddd2dd97-d639-4dae-a7ba-1553e860eb4b_1733652547.5224376.webp)\n\nhttps://youtu.be/uBoGo4P9t9E\n\n#### Join me on Telegram\n\nhttps://t.me/leetcode_daily_unstoppable/826\n\n#### Problem TLDR\n\nMax two non-overlapping intervals #medium #binary_search\n\n#### Intuition\n\nLet\'s observe some rich example and try to invent an algorithm:\n\n```j\n\n    // 0123456789111\n    //    .      012\n    // [.......7...]\n    // [.3][.2]   . \n    //  [.5][.3]  . \n    //   [.4][.4] . \n    //    [.2][.6]. \n    //    .[.1][.7] \n    //    ..  .   . \n    //    t.  .   .   t=3, v=3 maxV=3 maxT=3                        \n    //     t  .   .   t=4, v=5,maxV=5 maxT=4\n    //     .t .   .   t=5, v=4, \n    //     . t.   .   t=6, v=2\n    //     .  t   .   t=7, v=2\n    //     .  t   .   t=7, v=1\n    //     .  .t  .   t=8, v=3\n    //     .  . t .   t=9, v=4\n    //     .  .  t.   t=10,v=6, maxV=6, maxT=10\n    //     .  .  .t   t=11,v=7, maxV=7, maxT=11\n    //     .  .  . t  t=12,v=7\n    //    3555555677  maxV\n    //        *f  t   5+7\n\n\n```\nSome observations:\n* for current interval we should find the maximum before it\n* we can store the maximums as we go\n* we should sort events by the `end` times\n\nAnother two approaches:\n1. use a Heap, sort by start, pop from heap all non-intersecting previous and peek a max\n2. line sweep: put starts and ends in a timeline, sort by time, compute `max` after ends, and `res` on start\n\n#### Approach\n\n* binary search approach have many subtle tricks: add (0, 0) as zero, sort also by bigger values first to make binary search work\n\n#### Complexity\n\n- Time complexity:\n$$O(nlog(n))$$\n\n- Space complexity:\n$$O(n)$$\n\n#### Code\n\n```kotlin []\n\n    fun maxTwoEvents(events: Array<IntArray>): Int {\n        val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })\n        var res = 0; var max = 0;\n        for ((f, t, v) in events.sortedBy { it[0] }) {\n            while (pq.size > 0 && pq.peek().first < f) \n                max = max(max, pq.poll().second)\n            res = max(res, max + v)\n            pq += t to v\n        }\n        return res\n    }\n\n```\n```rust []\n\n    pub fn max_two_events(mut events: Vec<Vec<i32>>) -> i32 {\n        let (mut res, mut m) = (0, vec![(0, 0)]);\n        events.sort_unstable_by_key(|e| (e[1], -e[2]));\n        for e in events {\n            let i = m.partition_point(|x| x.1 < e[0]) - 1;\n            m.push((m.last().unwrap().0.max(e[2]), e[1]));\n            res = res.max(m[i].0 + e[2]);\n        }; res\n    }\n\n```\n```c++ []\n\n    int maxTwoEvents(vector<vector<int>>& events) {\n        vector<tuple<int, int, int>> t; int res = 0, m = 0;\n        for (auto e: events)\n            t.push_back({e[0], 1, e[2]}),\n            t.push_back({e[1] + 1, 0, e[2]});\n        sort(begin(t), end(t));\n        for (auto [x, start, v]: t)\n            start ? res = max(res, m + v) : m = max(m, v);\n        return res;\n    }\n\n```
['Binary Search', 'Line Sweep', 'Heap (Priority Queue)', 'C++', 'Rust', 'Kotlin']