Problem Overview

Given T time units and n tasks, each task i has a value a_i and a deadline b_i. In each time unit t, you may select one unselected task i where b_i ≥ t to gain a_i. The goal is to maximize the total reward.

Algorithm Strategy

Sort tasks in descending order of value a_i. Use a set to track available time slots. For each task, assign it to the latest possilbe time slot that does not exceed its deadline.

Complexity Analysis

Time compelxity is O(n log n) due to sorting and set operations.

Code Implementation

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef long long int64;
const int MAX_N = 2000010;

struct Task {
    int value, deadline;
    bool operator<(const Task &other) const {
        return value == other.value ? deadline > other.deadline : value > other.value;
    }
};

Task tasks[MAX_N];
set<int> time_slots;

int main() {
    int T, n;
    cin >> T >> n;
    int valid_count = 0;
    int64 total_reward = 0;
    for (int i = 0; i < n; i++) {
        int d, v;
        cin >> d >> v;
        if (d > n) {
            total_reward += v;
        } else {
            tasks[valid_count++] = {v, d};
        }
    }
    for (int i = 1; i <= n; i++) {
        time_slots.insert(i);
    }
    sort(tasks, tasks + valid_count);
    for (int i = 0; i < valid_count; i++) {
        auto it = time_slots.upper_bound(tasks[i].deadline);
        if (it == time_slots.begin()) continue;
        it--;
        total_reward += tasks[i].value;
        time_slots.erase(it);
    }
    cout << total_reward << endl;
    return 0;
}