Problem Statement

A teacher assigns all homework on the first day of school. Each homework assignment earns credits only if submitted before its deadline. Each assignment has a different deadline and credit value, and each assignment requires exactly one day to complete.

For example, if a assignment has 10 credits with a deadline of 6 days, you must submit it before the end of day 6 to earn those 10 credits.

Given the deadline and credit value for each of the N assignments, calculate the maximum credits obtainable by scheduling the assignments optimally.

Input Format

• First line: integer N (number of assignments)
• Next N lines: two integers per line — the deadline and the credit value for each assignment

Output Format

• Output a single integer: the maximum achievable credits (guaranteed to fit within long integer range)

Example

Input:

7
1 6
1 7
3 2
3 1
2 4
2 5
6 1

Output:

15

Algorithm Analysis

This problem can be solved using a greedy approach with a max-heap data structure.

Core Idea:

• Sort all assignments by deadline in descending order
• Iterate backwards through each day (from the latest deadline down to day 1)
• For each day, add all assignment whose deadline is greater than or equal to that day into a priority queue (max-heap)
• Always select and complete the assignment with the highest credit value from the available pool for that day

Why This Works: Working backwards from the latest deadline ensures that when we reach a particular day, we have considered all assignments that could possibly be completed on or before that day. By always picking the highest credit assignment available at each step, we maximize the total credits.

Correctness Proof

We prove this algorithm yields the maximum total credits using exchange argument.

Lemma: At any step when processing day d, if there exists an optimal schedule that completes some assignment with credits c on day d, and our algorithm selects an assignment with credits c' where c' ≥ c, then replacing the assignment with credits c in the optimal schedule with the assignment with credits c' produces another valid optimal schedule.

Proof: Since c' ≥ c and both assignments can be completed by day d (they are both in the priority queue), swapping them does not violate any deadline. The replaced assignment with credits c (which had lower or equal value) will be completed on a later day or not completed at all in the new schedule. Since c' ≥ c, the total credits do not decrease.

Theorem: The algorithm produces an optimal solution with maximum total credits.

Proof: Process days from the latest deadline backwards. At day d, our algorithm selects the assignment with maximum credits among all assignments not yet scheduled that can be completed by day d. By the lemma, any optimal solution can be transformed to include this assignment without reducing total credits. Applying this argument iteratively for each day ensures the final schedule is optimal.

Complexity Analysis

• Sorting assignments: O(N log N)
• Priority queue operations: O(N log N) (each assignment is inserted and removed at most once)
• Total time complexity: O(N log N)
• Space complexity: O(N) for storing assignments and the priority queue

Reference Implementation

#include <bits/stdc++.h>
using namespace std;

struct Assignment {
    int deadline;  // deadline
    int credit;    // credit value
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    
    vector<Assignment> tasks(n);
    for (int i = 0; i < n; ++i) {
        cin >> tasks[i].deadline >> tasks[i].credit;
    }
    
    // Sort by deadline in descending order
    sort(tasks.begin(), tasks.end(), [](const Assignment& a, const Assignment& b) {
        return a.deadline > b.deadline;
    });
    
    // Max-heap to always select the highest credit assignment
    priority_queue<int> creditHeap;
    
    long long totalCredits = 0;
    int currentIndex = 0;
    int maxDay = tasks[0].deadline;  // The latest deadline
    
    // Process from the latest day backwards
    for (int day = maxDay; day >= 1; --day) {
        // Add all assignments that can be completed by this day
        while (currentIndex < n && tasks[currentIndex].deadline >= day) {
            creditHeap.push(tasks[currentIndex].credit);
            ++currentIndex;
        }
        
        // Complete the highest credit assignment available
        if (!creditHeap.empty()) {
            totalCredits += creditHeap.top();
            creditHeap.pop();
        }
    }
    
    cout << totalCredits << endl;
    return 0;
}

Trace Through Example

Given assignments:

Sorted by deadline:

• Day 6: Assignment 7 (1 credit)
• Day 3: Assignments 3 (2 credits), 4 (1 credit)
• Day 2: Assignments 5 (4 credits), 6 (5 credits)
• Day 1: Assignments 1 (6 credits), 2 (7 credits)

Execution:

• Day 6: Heap contains [1] → pick 1
• Day 5: Heap empty → skip
• Day 4: Heap empty → skip
• Day 3: Add [2, 1] to heap → pick 2
• Day 2: Add [4, 5] to heap → pick 5
• Day 1: Add [6, 7] to heap → pick 7

Total: 1 + 2 + 5 + 7 = 15 credits