1996. The Number of Weak Characters in the Game

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character’s attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        map<int, multiset<int>> m;
        int res(0);
        for(auto& p : properties) {
            m[p[0]].insert(p[1]);
        }

        multiset<int> less;
        for(auto it = begin(m); it != end(m); it++) {
            auto lowerBound = less.lower_bound(*it->second.rbegin());
            if(lowerBound != begin(less)) {
                res += distance(begin(less), lowerBound);
                less.erase(begin(less), lowerBound);
            }
            less.insert(begin(it->second), end(it->second));
        }

        return res;
    }
};