1996. The Number of Weak Characters in the Game

T: O(nlogn + n)
S: O(n)

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] -  a[1];
            }
            return a[0] - b[0];
        });
        Deque<Integer> stack = new ArrayDeque<>();
        int result = 0;
        for (int[] property : properties) {
           while (!stack.isEmpty() && property[1] > stack.peek()) {
               stack.pop();
               result++;
           }
           stack.push(property[1]);
        }
        return result;
    }
}
/*
[[1,1],[2,1],[2,2],[1,2]]
[1,1], [1,2],[2,1],[2,2]


sort attack first, fix one value

then use mono stack, decreasing, if larger than peak, get the weak one 

but if attack equals, how we get the right ans?
ex:
[1,1], [1,2] -> in this case, we should not pop [1,1], because attack equals
the tricks is do the when attack equals, do defense sort by desc
-> become 

[1,2], [1,1] -> in this way, it wont pop, it's correct

T: O(nlogn + n)
S: O(n)
*/ja

using Heap

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        att_defs = defaultdict(list) # {1:[5],4:[3],10:[4]}
        for at, df in properties:
            att_defs[at].append(df)
        min_heap_def = [] # [5]
        res = 0 # 1
        for at in sorted(att_defs.keys()): # 10  [[1,5],[4,3]] [10,4]. 5 3 4
            for df in att_defs[at]: # df:4
                while min_heap_def and df > min_heap_def[0]:
                    res += 1
                    heapq.heappop(min_heap_def)
            for df in att_defs[at]:
                heapq.heappush(min_heap_def, df)
        return res