Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間1年前 (2024/12/08 16:21)推噓1(1推 0噓 0→)

https://leetcode.com/problems/two-best-non-overlapping-events 2054. Two Best Non-Overlapping Events 給你一個陣列表示活動 events[i] = [startTimei, endTimei, valuei]，你最多可以參加兩個活動，活動持續期間不可參加其他活動，求出最多可以獲得的value。思路： 1.先把陣列按照活動結束時間排序。 2.每次參加活動i的時候就往前去找一個活動 j 滿足 events[j].endtime < events[i].startTime 因為有單調性所以可以用二分搜索。 3.前面的活動要用一個陣列保存最大的value讓二分搜索保持單調性： [1,2,3,4] [1,2] [1,2,3,4,5] => [1,2,3,4] [4,4] [4,4,4,4,5] 所以我們只要找滿足條件的最右活動即可 Java code: ---------------------------------------- class Solution { public int maxTwoEvents(int[][] events) { Arrays.sort(events, Comparator.comparingInt(e -> e[1])); int n = events.length; int[] dp = new int[n]; dp[0] = events[0][2]; int res = dp[0]; for (int i = 1; i < n; i++) { res = Math.max(res, events[i][2]); dp[i] = Math.max(dp[i - 1], events[i][2]); int l = 0, r = i - 1; while (l <= r) { int mid = (l + r)/2; if (events[mid][1] < events[i][0]) { l = mid + 1; } else { r = mid - 1; } } if (r > -1) { res = Math.max(res, dp[r] + events[i][2]); } } return res; } } ---------------------------------------- -- https://i.imgur.com/ZfdGodg.jpeg