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):

if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[1], reverse=True)
    income = 0
    daysUsed = -1
    for job in jobs:
        daysLeft = (m - daysUsed) - job[0]
        if daysLeft > 0:
            income += job[1]
            daysUsed += 1
        else:
            income += job[1]
            break
    print(income)



if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[1], reverse=True)
    print("+++++++")
    print(jobs)
    print("+++++++")
    income = 0
    daysUsed = -1
    for job in jobs:
        daysLeft = (m - daysUsed) - job[0]
        if daysLeft > 0:
            print(job)
            print((m - daysUsed) - job[0])
            income += job[1]
            daysUsed += 1
        else:
            income += job[1]
            break
    print(income)


from sys import exit
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[1], reverse=True)
    income = 0
    daysUsed = -1
    if len(jobs) == 0:
        print(0)
        exit()

    for job in jobs:
        daysLeft = (m - daysUsed) - job[0]
        if daysLeft > 0:
            income += job[1]
            daysUsed += 1
        else:
            income += job[1]
            break
    print(income)


from sys import exit
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[1], reverse=True)
    income = 0
    daysUsed = -1
    if m == 1:
        print(jobs[0][1])
        exit()
        
    for job in jobs:
        daysLeft = (m - daysUsed) - job[0]
        if daysLeft > 0:
            income += job[1]
            daysUsed += 1
        else:
            income += job[1]
            break
    print(income)


from sys import exit
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[1], reverse=True)
    income = 0
    daysUsed = -1
    if m == 1:
        print(jobs[1])
        exit()

    for job in jobs:
        daysLeft = (m - daysUsed) - job[0]
        if daysLeft > 0:
            income += job[1]
            daysUsed += 1
        else:
            income += job[1]
            break
    print(income)


from sys import exit
from collections import deque
import heapq
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[0])
    income = 0
    jobs = deque(jobs)
    hp = []
    for day in range(m):
        while len(jobs) != 0 and jobs[0][0] <= day + 1:
            job = jobs[0]
            heapq.heappush(hp, - job[1])
            jobs.popleft()
        if hp != []:
            income -= heapq.heappop(hp)
    
    print(income)


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Accepted