2856. Minimum Array Length After Pair Removals

You are given a 0-indexed sorted array of integers nums.

You can perform the following operation any number of times:

• Choose two indices, i and j, where i < j, such that nums[i] < nums[j].
• Then, remove the elements at indices i and j from nums. The remaining elements retain their original order, and the array is re-indexed.

Return an integer that denotes the minimum length of nums after performing the operation any number of times (including zero).

class Solution {
public:
    int minLengthAfterRemovals(vector<int>& nums) {
        multimap<int,int> match;
        priority_queue<int,vector<int>,greater<int>> q;
        for(auto x : nums) {
            if(q.size() and q.top() < x) {
                match.insert(make_pair(x, q.top()));
                q.pop();
            } else {
                auto it = match.lower_bound(x);
                if(it == begin(match)) {
                    q.push(x);
                } else {
                    --it;
                    auto [k,v] = *it;
                    match.insert(make_pair(x,k));
                    q.push(v);
                    match.erase(it);
                }
            }
        }
        return q.size();
    }
};