Description

Submission

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        map<int, vector<int>> Map;

        for(auto& p: properties) {
            Map[p[0]].push_back(p[1]);
        }

        int currentMax = 0;

        int ret = 0;
        for(auto it = Map.rbegin(); it != Map.rend(); ++it) {
            int a = it->first;
            auto& bs = it->second;

            sort(bs.begin(), bs.end());

            if(currentMax != 0) {
                auto it = upper_bound(bs.begin(), bs.end(), currentMax-1);
                ret += it - bs.begin();
            }

            // update currentMax
            currentMax = max(currentMax, *max_element(bs.begin(), bs.end()));
        }

        return ret;
    }
};

// [[3,6],[5,5],[6,3]]

// [[1,1],[2,1],[2,2],[1,2]]
// [1,1][2,1]
// [1,2][2,2]

// [[7,9],[10,7],[6,9],[10,4],[7,5],[7,10]]


// 6: 9
// 7: 5 9 10
// 10: 4 7