1996. The Number of Weak Characters in the Game

This is my first time try to use English write article.

If has any question, please contact with me. Thanks.

This problem is hard to find the solution, how to solve it,

First, we do sort with first element, and if the first element are same, we need to decide the order by second element, and the order is opposite by first one

like this

[1,1],[1,2],[2,2],[2,1]
=>
[1,2],[1,1],[2,2],[2,1]
first element is increasing, and if first element are same, 
we sort by second element decreasing.

so we traverse it sorted array from last element, and check only second element.If there are existed, A[1] > B[1],

we must can ensure A stronger than B, why? because first element sort by increasing, that ensure A[0] ≥ B[0]. And when A[0] == B[0] we can ensure that doesn’t happen A[1] > B[1], because we sort second element opposite.

so the code is:

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& pts) {
        sort(pts.begin(), pts.end(),  [](auto &a, auto &b){
            if(a[0] == b[0]){
                return a[1] > b[1];
            }
            return a[0] < b[0];
        });
        int res = 0;
        int mn = INT_MIN;
        for(int i = pts.size() - 1; i>=0;i--){
            if(pts[i][1] < mn){
                res++;
            }
            mn = max(pts[i][1], mn);
        }
        return res;
    }
};

Time Complexity: O(n log n)