Maximum Profit Scheduling Problem

This problem addresses the optimization of sales revenue for a set of products, where each item possesses a specific profit margin and a hard expiration deadline. You possess a capacity to sell exactly one product per day. Once a product's deadline has passed, it cannot be sold. The objective is to determine the sequence of sales that yields the highest possible cumulative profit.

Input Specification

The input consists of multiple test cases processed sequentially until the end of the file. Each test case begins with an integer n, representing the number of products available. Following this, there are n pairs of integers provided. Each pair corresponds to a single product and consists of:

• Profit (p): The revenue generated by selling the item.
• Deadline (d): The day by which the item must be sold (inclusive).

Data may be separated by arbitrary whitespace or newlines. The input is guaranteed to be well-formed.

Output Specification

For each distinct dataset, output a single integer representing the calculated maximum total profit achievable under optimal scheduling.

Constraints

• Number of items n: 0 ≤ n ≤ 100,000
• Profit and Deadline values: 1 ≤ p, d ≤ 10,000
• Maximum number of test cases: 14

Example

Input:
4 50 2 10 1 20 2 30 1

7 20 1 2 1 10 3 100 2 8 2
5 20 50 10

Output:
80
185

Algorithmic Approach

To solve this efficiently, we utilize a Greedy strategy combined with a Maximum Heap (Priority Queue). The core logic relies on processing time slots backward from the latest possible deadline to day 1. By working backwards, for any given day t, we know that any item with a deadline greater then or equal to t can still be validly scheduled on or before that day.

At each day starting from the maximum deadline, we gather all items whose deadlines coincide with that day. These candidates are added to a priority queue sorted by profit. From the queue, we select the item with the highest profit for the current time slot and remove it from consideration. This ensures that high-value items are secured in available slots without unnecessarily blocking slots reserved for other potential items.

Implementation

The following C++ implementation demonstrates the described strategy. It utilizes a bucket-sorting mechanism based on deadlines and a min-max heap to manage candidate selections dynamically.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// Define maximum possible deadline based on constraints
const int MAX_D = 10005;

void solve() {
    int n;
    // Read input until EOF
    while (cin >> n) {
        // Vector of vectors to store profits for each specific deadline
        vector<int> deadlines[MAX_D];
        int max_d = 0;

        for (int i = 0; i < n; ++i) {
            int profit_val, deadline_day;
            cin >> profit_val >> deadline_day;
            
            // Track the maximum deadline encountered
            if (deadline_day > max_d) {
                max_d = deadline_day;
            }
            
            // Store profit in the bucket corresponding to its deadline
            if (deadline_day < MAX_D) {
                deadlines[deadline_day].push_back(profit_val);
            }
        }

        // Min-max priority queue to access the largest element quickly
        priority_queue<int> pq;
        long long total_revenue = 0;

        // Iterate backwards from the latest possible deadline
        for (int day = max_d; day > 0; --day) {
            // Add all items expiring on this day to the priority queue
            for (auto profit : deadlines[day]) {
                pq.push(profit);
            }

            // If available items exist, sell the most profitable one for this day
            if (!pq.empty()) {
                total_revenue += pq.top();
                pq.pop();
            }
        }

        cout << total_revenue << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}