Problem: There are N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of B_i after A_i days from the day you do it.  You can take and complete at most one of these jobs in a day.  However, you cannot retake a job that you have already done.  Find the maximum total reward that you can earn no later than M days from today.  You can already start working today.

Submission attempts (in order):
import bisect

n, m = map(int, input().split())
a_list = []
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        a_list.append([a, b])
a_list = sorted(a_list, key=lambda x: (x[0], -x[1]))
a_list_1 = [aa[0] for aa in a_list]
a_list_2 = [aa[1] for aa in a_list]
ans = 0
for i in range(m):
    k = bisect.bisect_right(a_list_1, m - i) - 1
    if k >= 0:
        l = k
        if l < len(a_list_2):
            if a_list_1[l] <= m - i:
                ans += a_list_2[l]
                del a_list_1[l], a_list_2[l]
print(ans)


import bisect

n, m = map(int, input().split())
a_list = []
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        a_list.append([a, b])
a_list = sorted(a_list, key=lambda x: (x[0], -x[1]))
a_list_1 = [aa[0] for aa in a_list]
a_list_2 = [aa[1] for aa in a_list]
ans = 0
for i in range(m):
    k = bisect.bisect_right(a_list_1, m - i) - 1
    if k >= 0:
        l = len(a_list_2) - reversed(a_list_2).index(max(a_list_2[:k + 1])) - 1
        if l < len(a_list_2):
            if a_list_1[l] <= m - i:
                ans += a_list_2[l]
                del a_list_1[l], a_list_2[l]
print(ans)

n, m  = map(int, input().split())
red = []
blue = []
for _ in range(n):
    a, b = map(int, input().split())
    red.append([a, b])
for i in range(m):
    c, d = [i, 0]
    blue.append([c, d])
blue.sort()
red.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b in blue:
    for i, r in enumerate(red):
        if (r[0] < b[0]) & (r[1] < b[1]):
            ans += 1
            red.pop(i)
            break
print(ans)

n = int(input())
red = []
blue = []
for _ in range(n):
    a, b = map(int, input().split())
    red.append([a, b])
for i in range(n):
    c, d = [i, 0]
    blue.append([c, d])
blue.sort()
red.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b in blue:
    for i, r in enumerate(red):
        if (r[0] < b[0]) & (r[1] < b[1]):
            ans += 1
            red.pop(i)
            break
print(ans)

import bisect

n, m = map(int, input().split())
a_list = []
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        a_list.append([a, b])
a_list = sorted(a_list, key=lambda x: (x[0], -x[1]))
a_list_1 = [aa[0] for aa in a_list]
a_list_2 = [aa[1] for aa in a_list]
ans = 0
for i in range(m):
    k = bisect.bisect_right(a_list_1, m - i) - 1
    if k >= 0:
        l = len(a_list_2) - reversed(a_list_2).index(max(a_list_2[:k + 1])) - 1
        if a_list_1[l] <= m - i:
            ans += a_list_2[l]
            del a_list_1[l], a_list_2[l]
print(ans)

import bisect

n, m = map(int, input().split())
a_list = []
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        a_list.append([a, b])
a_list = sorted(a_list, key=lambda x: (x[0], -x[1]))
a_list_1 = [aa[0] for aa in a_list]
a_list_2 = [aa[1] for aa in a_list]
ans = 0
for i in range(m):
    k = bisect.bisect_right(a_list_1, m - i) - 1
    if k >= 0:
        l = bisect.bisect_right(a_list_2[:k + 1], max(a_list_2[:k + 1])) - 1
        if a_list_1[l] <= m - i:
            ans += a_list_2[l]
            del a_list_1[l], a_list_2[l]
print(ans)

from collections import defaultdict
import heapq

a_dict = defaultdict(lambda: [])
n, m = map(int, input().split())
for _ in range(n):
    a, b = map(int, input().split())
    a_dict[a].append(-b)
ans = 0
heap_list = []
for i in range(1, m + 1):
    for aa in a_dict[i]:
        heapq.heappush(heap_list, aa)
    if len(heap_list) > 0:
        ans -= heapq.heappop(heap_list)
print(ans)

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Accepted