M - Most Ordered Way

/*
 * Author: Matheus Monteiro
 */

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;

    cin >> n;

    vector<int> duration(n);
    vector<int> deadline(n);

    for(int i = 0; i < n; ++i) {
        cin >> duration[i] >> deadline[i];
    }

    vector<int> position(n);
    iota(position.begin(), position.end(), 0);

    sort(position.begin(), position.end(), [&](int task1, int task2) {
        return deadline[task1] < deadline[task2];
    });

    long long currentTime = 0;
    vector<bool> performedTask(n, false);
    vector<int> smallestPermutation;

    for(int i = 0; i < n; ++i) {
        int bestJ = -1;
        long long minGap = numeric_limits<long long>::max();
        long long acumulatedDuration = 0;
        for(const int &jPos : position) {
            if(!performedTask[jPos]) {
                if(duration[jPos] <= minGap && (bestJ == -1 || jPos < bestJ)) {
                    bestJ = jPos;
                }
                minGap = min(deadline[jPos] - duration[jPos] - currentTime - acumulatedDuration, minGap);
                acumulatedDuration += duration[jPos];
            }
        }

        if(bestJ == -1) {
            cout << "*\n";
            return;
        }

        currentTime += duration[ bestJ ];
        smallestPermutation.push_back(bestJ);
        performedTask[bestJ] = true;
    }

    currentTime = 0;
    for(const int &num : smallestPermutation) {
        currentTime += duration[num];
        if(currentTime > deadline[num]) {
            cout << "*\n";
            return;
        }
    }

    for(const int &num : smallestPermutation)
        cout << num + 1 << ' ';
    cout << endl;
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int numTestCases = 1;
    // std::cin >> numTestCases;
    for(int testCase = 1; testCase <= numTestCases; ++testCase) {
        // cout << "Case #" << testCase << ": ";
        solve();
    }

    return 0;
}