# 2054. Two Best Non-Overlapping Events
###### tags: `Leetcode` `Medium` `Line Sweep` `Greedy` `Sorting`
Link: https://leetcode.com/problems/two-best-non-overlapping-events/description/
## 思路
### Line Sweep
### Greedy Sorting
map里面存的是在key及key之前结束的event的最大value
所以我们要先将所有event按照结束时间排序
然后对于每一个新的event 我们看看map里面有没有在它之前 并且不跟他重叠的event 更新答案
然后要看要不要用这个新的event更新map
也就是我们要看有没有key比当前event的end time早或者相等 如果有的话 看它的value是多少
如果value比当前value大 说明我们不需要更新 否则就需要更新
## Code
### Line Sweep

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        line = []
        ans = 0
        for s, e, v in events:
            line.append((s, True, v))
            line.append((e+1, False, v))
        line.sort()
        currMax = 0
        for time, is_start, val in line:
            if is_start:
                ans = max(ans, currMax+val)
            else:
                currMax = max(currMax, val)
        return ans

### Greedy Sorting

class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a,b)->(a[1]-b[1]));
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int ans = 0;
        for(int[] event: events){
            int start = event[0], end = event[1], val = event[2];
            Integer smallerThanStart = map.lowerKey(start);
            if(smallerThanStart==null) ans = Math.max(ans, val);
            else ans = Math.max(ans, map.get(smallerThanStart)+val);
            Integer smOrEqThanEnd = map.floorKey(end);
            if(smOrEqThanEnd==null) map.put(end, val);
            else map.put(end, Math.max(map.get(smOrEqThanEnd), val));
        }
        return ans;
    }
}