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 collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi], reverse = True)
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    for bi in rewards:
        for i in range(m-1, -1, -1):
            if busy[i] == 0:
                while d[bi] and d[bi][-1] > m-i:
                    d[bi].pop()
                if d[bi]:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    # print(ai, bi)
                else:
                    break
    return ans

import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi], reverse = True)
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    print(d)
    for bi in rewards:
        for i in range(m-1, -1, -1):
            if busy[i] == 0:
                if d[bi] and d[bi][-1] <= m-i:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    # print(ai, bi)

    return ans

if __name__ == '__main__':
    print(main())

import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi], reverse = True)
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    for bi in rewards:
        for i in range(m-1, -1, -1):
            if busy[i] == 0:
                while d[bi] and d[bi][-1] > m-i:
                    d[bi].pop()
                if d[bi]:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    # print(ai, bi)
                else:
                    break
    return ans

if __name__ == '__main__':
    print(main())

import collections
def main():
    nm = input().split()
    n, m = int(nm[0]), int(nm[1])

    d = collections.defaultdict(list)
    for i in range(n):
        ab = input().split()
        ai, bi = int(ab[0]), int(ab[1])
        d[bi].append(ai)
    for bi in d:
        d[bi] = sorted(d[bi])
    rewards = sorted(list(d.keys()), reverse = True)

    busy = [0 for _ in range(m)]
    ans = 0
    for bi in rewards:
        for i in range(m):
            if busy[i] == 0:
                while d[bi] and d[bi][-1] > m-i:
                    d[bi].pop()
                if d[bi]:
                    busy[i] = 1
                    ans += bi
                    ai = d[bi].pop()
                    print(ai, bi)
                else:
                    break
    return ans

if __name__ == '__main__':
    print(main())

import heapq
def main():

    N, M = map(int, input().split())
    task = []
    for _ in range(N):
        A, B = map(int, input().split())
        task.append([A, B])
    task.sort()

    hq = []
    ans = 0
    for i in range(1, M+1):
        while task and task[0][0]<= i:
            _, v = heapq.heappop(task)
            heapq.heappush(hq, -v)
        if hq:
            v = heapq.heappop(hq)
            ans += -v
    return ans

if __name__ == '__main__':
    print(main())

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted