Sorting, MaxHeap and Partial-Difference Array
Sorting and Max Heap\npython []\nclass Solution:\n    # O(n + mlogm) time | O(n + m) space\n    # n = length of nums\n    # q = length of queries\n    def maxRe
# Sorting and Max Heap\n```python []\nclass Solution:\n    # O(n + mlogm) time | O(n + m) space\n    # n = length of nums\n    # q = length of queries\n    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:\n        n, m = len(nums), len(queries)\n\n        queries.sort()\n        q_idx = 0\n        max_heap = []\n        end_deltas = [0] * (n + 1)\n        total_possible_change = 0\n\n        for i in range(n):\n            total_possible_change += end_deltas[i]\n\n            # add all possible intervals that start <= i\n            # to max heap tracking their ends\n            while q_idx < m and queries[q_idx][0] <= i:\n                heappush(max_heap, -1 * queries[q_idx][1])\n                q_idx += 1\n\n            while nums[i] - total_possible_change > 0:\n                if not max_heap:\n                    return -1\n\n                # all queries in the max heap are guaranteed to have start <= i\n                # but doesn\'t mean they\'ll have an i <= end\n                farthest_end = max_heap[0] * -1\n                if i > farthest_end:\n                    return -1\n\n                # apply the best query and mark where this\n                # query stops taking affect\n                heappop(max_heap)\n                total_possible_change += 1\n                end_deltas[farthest_end + 1] -= 1\n\n        return len(max_heap)\n\n```\n\n---\n\n# Min Heap and Max Heap\n``` Python []\nclass EarlierStartInterval:\n    def __init__(self, start, end):\n        self.start = start\n        self.end = end\n\n    def __lt__(self, other):\n        return self.start < other.start\n\n    def __iter__(self):\n        yield self.start\n        yield self.end\n\n\nclass LaterEndInterval:\n    def __init__(self, start, end):\n        self.start = start\n        self.end = end\n\n    def __lt__(self, other):\n        return self.end > other.end\n\n    def __iter__(self):\n        yield self.start\n        yield self.end\n\n\nclass Solution:\n    # O(n + mlogm) time | O(n + m) space\n    # n = length of nums\n    # q = length of queries\n    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:\n        n = len(nums)\n\n        earliest_starts = []\n        latest_ends = []\n\n        for q in queries:\n            heappush(earliest_starts, EarlierStartInterval(q[0], q[1]))\n\n        end_deltas = [0] * (n + 1)\n        total_possible_change = 0\n\n        for i in range(n):\n            total_possible_change += end_deltas[i]\n\n            while earliest_starts and earliest_starts[0].start <= i:\n                start, end = heappop(earliest_starts)\n                heappush(latest_ends, LaterEndInterval(start, end))\n\n            while nums[i] - total_possible_change > 0:\n                if not latest_ends or latest_ends[0].end < i:\n                    return -1\n\n                _, end = heappop(latest_ends)\n                end_deltas[end + 1] -= 1\n                total_possible_change += 1\n\n        return len(latest_ends)\n```
['Array', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'Prefix Sum', 'Python3']