<p>You are playing a game that contains multiple characters, and each of the characters has <strong>two</strong> main properties: <strong>attack</strong> and <strong>defense</strong>. You are given a 2D integer array <code>properties</code> where <code>properties[i] = [attack<sub>i</sub>, defense<sub>i</sub>]</code> represents the properties of the <code>i<sup>th</sup></code> character in the game.</p>

<p>A character is said to be <strong>weak</strong> if any other character has <strong>both</strong> attack and defense levels <strong>strictly greater</strong> than this character&#39;s attack and defense levels. More formally, a character <code>i</code> is said to be <strong>weak</strong> if there exists another character <code>j</code> where <code>attack<sub>j</sub> &gt; attack<sub>i</sub></code> and <code>defense<sub>j</sub> &gt; defense<sub>i</sub></code>.</p>

<p>Return <em>the number of <strong>weak</strong> characters</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> properties = [[5,5],[6,3],[3,6]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> No character has strictly greater attack and defense than the other.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> properties = [[2,2],[3,3]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The first character is weak because the second character has a strictly greater attack and defense.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> properties = [[1,5],[10,4],[4,3]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The third character is weak because the second character has a strictly greater attack and defense.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= properties.length &lt;= 10<sup>5</sup></code></li>
	<li><code>properties[i].length == 2</code></li>
	<li><code>1 &lt;= attack<sub>i</sub>, defense<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

# [[1,5],[10,4],[4,3],[11,2]]
# [[1,5],[4,3],[10,2],[11,2],...,[1231232,4]]
# [[10,2],[11,2],....,[4,3],[1231232,4],[1,5]]

# [[5,5],[6,3],[3,6]]
# [[3,6],[5,6],[5,5],[6,3]]
# [[6,3],[5,5],[3,6]]

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

# n * (create set + binary search + create set + intersection)
# n * (n + logn + n + n) -> n log n

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda x: x[1], reverse=True)
        properties.sort(key=lambda x: x[0])
        
        n = len(properties)
        count = 0
        max_defense = properties[-1][1]
        attack_of_max_defense = properties[-1][0]
        
        for i in range(n):
            c = properties[n-1-i]
            if c[1] < max_defense and c[0] < attack_of_max_defense:
                count += 1
            elif c[1] > max_defense:
                max_defense = c[1]
                attack_of_max_defense = c[0]
        
        return count



    def numberOfWeakCharacters_BRUTE_WITH_SORT(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda x: x[0])
        count = 0
        for i in range(len(properties)):
            is_weak = False
            for j in range(i+1, len(properties)):
                if properties[i][0] < properties[j][0] and \
                    properties[i][1] < properties[j][1]:
                    is_weak = True
                    break
            if is_weak:
                count += 1
        return count


    # Brute force
    def numberOfWeakCharacters_BRUTE(self, properties: List[List[int]]) -> int:
        count = 0
        for i in range(len(properties)):
            is_weak = False
            for j in range(len(properties)):
                if i != j:
                    if properties[i][0] < properties[j][0] and \
                        properties[i][1] < properties[j][1]:
                        is_weak = True
                        break
            if is_weak:
                count += 1
        return count
1620