Description

Submission

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), [](vector<int>& v1, vector<int>& v2) {
            return v1[1] < v2[1];
        });

        map<int, int> largest;
        
        int ret = 0;
        int tmpMax = 0;
        for(auto& event: events) {
            int startTime = event[0];
            int endTime = event[1];
            int value = event[2];

            tmpMax = max(tmpMax, value);
            largest[endTime] = tmpMax;
        }

        for(auto& event: events) {
            int startTime = event[0];
            int endTime = event[1];
            int value = event[2];
            
            ret = max(ret, value);

            auto it = largest.upper_bound(startTime - 1);
            if(it != largest.begin()) {
                --it;
                ret = max(it->second + value, ret);
            }   
        }

        return ret;
    }
};

// largest[x]: largest value ended by x
// [[1,3,2],[1,5,5],[4,5,2]]