1996. number of weak characters in the game

topic ： Roles have two properties , Attack and defense . When the character's attack and defense are strictly smaller than that of a certain character , Then the role is “ Weak role ”. In the array “ Weak role ” Number .

Explain : This problem can sort the array by attack , Then compare defense . Remember that the current biggest defensive role is q, The currently accessed role is p.

If q defense >p defense , And q attack >p attack , that p Namely “ Weak role ”.

One problem is , How to ensure q defense > p Defensive time ,q attack also > p attack ？

The method given in the solution , Sort by attack descending , Attack at the same time , In ascending defense order .

It can be proved to the contrary ：

hypothesis ： If q Defense ratio p Big , And q Attack and p The attack is the same .

from ” Attack at the same time , In ascending defense order “ You know q It must be p Back .

But when we traverse from front to back q It must be p front , Wrong assumption .

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda x: (-x[0], x[1])) # Attack descending , Defense ascending 
        ans = 0
        maxDef = 0
        for _, def_ in properties:
            if maxDef > def_:
                ans += 1
            else:
                maxDef = max(maxDef, def_)
        return ans