# 2054. Two Best Non-Overlapping Events

• Time: $O(\texttt{sort})$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 struct Event { int time; int value; bool isStart; Event(int time, int value, bool isStart) : time(time), value(value), isStart(isStart) {} }; class Solution { public: int maxTwoEvents(vector>& events) { int ans = 0; int maxValue = 0; vector evts; for (const auto& event : events) { const int start = event[0]; const int end = event[1]; const int value = event[2]; evts.emplace_back(start, value, true); evts.emplace_back(end + 1, value, false); } sort(begin(evts), end(evts), [](const auto& a, const auto& b) { return a.time == b.time ? a.isStart < b.isStart : a.time < b.time; }); for (const auto& [_, value, isStart] : evts) if (isStart) ans = max(ans, value + maxValue); else maxValue = max(maxValue, value); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Event { public int time; public int value; public int isStart; public Event(int time, int value, int isStart) { this.time = time; this.value = value; this.isStart = isStart; } }; class Solution { public int maxTwoEvents(int[][] events) { int ans = 0; int maxValue = 0; Event[] evts = new Event[events.length * 2]; for (int i = 0; i < events.length; ++i) { final int start = events[i][0]; final int end = events[i][1]; final int value = events[i][2]; evts[i * 2] = new Event(start, value, 1); evts[i * 2 + 1] = new Event(end + 1, value, 0); } Arrays.sort(evts, (a, b) -> a.time == b.time ? a.isStart - b.isStart : a.time - b.time); for (Event evt : evts) if (evt.isStart == 1) ans = Math.max(ans, evt.value + maxValue); else maxValue = Math.max(maxValue, evt.value); return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution: def maxTwoEvents(self, events: List[List[int]]) -> int: ans = 0 maxValue = 0 evts = [] # (time, isStart, value) for s, e, v in events: evts.append((s, 1, v)) evts.append((e + 1, 0, v)) # When two events have the same time, the one is not start will be in the front evts.sort() for _, isStart, value in evts: if isStart: ans = max(ans, value + maxValue) else: maxValue = max(maxValue, value) return ans