Условие задачи

Есть программист, которому нужно выполнить $n$-ое количество заказов. У каждого заказа есть срок - $di$ и штраф - $fi$ ($di$, $fi$ - положительные целые числа). Штраф начисляется, если выполнить заказ позже срока. Чтобы выполнить заказ, нужна ровно одна единица времени. Выполнение первого заказа начинается в момент времени $0$ и заканчивается в момент времени $1$, выполнение второго заказа начинается в момент времени $1$ и заканчивается в момент времени $2$ и т. д. Нужно найти расписание, при котором сумма штрафов будет минимальной.

---

Решение

Нам всегда выгодны заказы с наибольшими штрафами — тогда сумма штрафов будет минимальна. Осталось понять, как распределить заказы.

Будем перебирать заказы в порядке убывания штрафов и заполнять расписание следующим образом: если для заказа есть еще хотя бы одно свободное место в расписании раньше его срока, то поставим его на самое последнее из таких мест, иначе в срок заказ выполнен не будет, поэтому поставим его в конец из свободных мест.

---

Сложность

Сложность алгоритма - $O(n) + n*log_2 n$, где $n$ - количество заказов.

---

Псевдокод

Аннотация:
deadline - срок выполнения заказа
fine - штраф за просрочку заказа
number - номер заказа

Функция F(fines, deadlines, number)
    сортируем заказы по убыванию штрафов

    просроченные_заказы <- пустой список
    выполненные_заказы <- пустой список

    для time в диапозоне от 0 до максимального срока
        если time < срок заказа
            то добавляем заказ в выполненные_заказы
        иначе
            добавляем заказ в просроченные_заказы
            
    сортируем выполненные_заказы по возрастанию сроков

    ответ <- выполненные_заказы + просроченные_заказы

    вернуть ответ

---

Реализация на Python

Аннотация:
Order - класс, представляющий заказ
deadline - срок выполнения заказа
fine - штраф за просрочку заказа
number - номер заказа
init - инициализация списка заказов и их сортировка по убыванию штрафов
deadlines - список сроков выполнения заказов
fines - список штрафов за просрочку заказов
n - количество заказов
orders - список объектов класса Order
sort_order - сортировка выполненных заказов по срокам выполнения
complete_orders - список выполненных заказов
new_complete_orders - список номеров выполненных заказов, отсортированных по срокам выполнения
make_schedule - создание расписания выполнения заказов
deadlines - список сроков выполнения заказов
fines - список штрафов за просрочку заказов
n - количество заказов
overdue_orders - список номеров просроченных заказов
complete_orders - список выполненных заказов
orders - список заказов, отсортированных по штрафам

class Order:  
    def __init__(self, deadline, fine, number):  
        self.deadline = deadline  
        self.fine = fine  
        self.number = number  
  

def init(deadlines, fines, n):  
    orders = list()  
    
    for num_order in range(n):  
        order = Order(deadlines[num_order], 
                      fines[num_order], num_order+1)  
        orders.append(order)  
        
    return sorted(orders, key=lambda x: x.fine, reverse=True)  

def sort_order(complete_orders):  
    new_complete_orders = list()  
    complete_orders = sorted(complete_orders, key=lambda x: x.deadline)  
    
    for order in complete_orders:  
        new_complete_orders.append(order.number)  
        
    return new_complete_orders  

def make_schedule(deadlines, fines, n):  
    overdue_orders, complete_orders = list(), list()  
    orders = init(deadlines, fines, n)  
    num_order = 0  
    
    for time in range(max(deadlines)+1):  
        if num_order < n:  
            curr_order = orders[num_order]  
            
            if time <= curr_order.deadline:  
                complete_orders.append(curr_order)  
                
            else:  
                overdue_orders.append(curr_order.number) 
                 
            num_order += 1 
             
    complete_orders = sort_order(complete_orders)
      
    return complete_orders + overdue_orders

---

Олимпиадная реализация на C++

Аннотация:
comp_fine - функция для сравнения заказов по штрафам, возвращающая `true`, если штраф первого заказа больше штрафа второго.
ord_1 - первый заказ (вектор из трех элементов: срок, штраф и номер).
ord_2 - второй заказ (вектор из трех элементов: срок, штраф и номер).
init - инициализация списка заказов и их сортировка по убыванию штрафов.
dl - вектор сроков выполнения заказов.
fines - вектор штрафов за просрочку заказов.
n - количество заказов.
ord - вектор векторов, каждый из которых содержит срок, штраф и номер заказа.
comp_dl - функция для сравнения заказов по срокам выполнения, возвращающая `true`, если срок первого заказа меньше срока второго.
sort_ord - сортировка выполненных заказов по срокам выполнения.
best_ord - вектор выполненных заказов.
begin - вектор номеров выполненных заказов, отсортированных по срокам выполнения.
make_schedule - создание расписания выполнения заказов.
end - вектор номеров просроченных заказов.
ans - вектор номеров всех заказов в порядке их выполнения.
num_ord - текущий номер обрабатываемого заказа.
t - максимальный срок выполнения заказа плюс один.

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

bool comp_fine(vi ord_1, vi ord_2) {
    return ord_1[1] > ord_2[1];
}

vvi init(vi dl, vi fines, int n) {
    vvi ord;
    for (int i = 0; i < n; i++) {
        vi ord_ = { dl[i], fines[i], i + 1 };
        ord.push_back(ord_);
    }
    sort(ord.begin(), ord.end(), comp_fine);
    return ord;
}

bool comp_dl(vi ord_1, vi ord_2) {
    return ord_1[0] < ord_2[0];
}

vi sort_order(vvi best_ord) {
    vi begin;
    sort(best_ord.begin(), best_ord.end(), comp_dl);
    for (vi ord : best_ord) {
        begin.push_back(order[2]);
    }
    return begin;
}

vi make_schedule(vi dl, vi fines, int n) {
    vi end, ans;
    vvi best_ord;
    vvi ord = init(dl, fines, n);
    int num_ord = 0;
    int t = *max_element(dl.begin(), dl.end())+1;
    for (int i = 0; i < t; i++) {
        if (num_ord < n) {
            vi curr_ord = ord[num_ord];
            if (i <= curr_ord[0]) {
                best_ord.push_back(curr_ord);
            }
            else {
                end.push_back(curr_ord[2]);
            }
            num_ord += 1;
        }
    }
    vi begin = sort_ord(best_ord);
    ans.insert(ans.begin(), begin.begin(), begin.end());
    ans.insert(ans.end(), end.begin(), end.end());
    return ans;
}

---

Продуктовая реализация на C++

Аннотация:
Order - класс, представляющий заказ.
deadline - срок выполнения заказа.
fine - штраф за просрочку заказа.
number - номер заказа.
compare_for_fine - функция для сравнения заказов по штрафам, возвращающая `true`, если штраф первого заказа больше штрафа второго.
order_1 - первый заказ.
order_2 - второй заказ.
init - инициализация списка заказов и их сортировка по убыванию штрафов.
deadlines - вектор сроков выполнения заказов.
fines - вектор штрафов за просрочку заказов.
number_orders - количество заказов.
orders - вектор объектов класса Order.
compare_for_deadline - функция для сравнения заказов по срокам выполнения, возвращающая `true`, если срок первого заказа меньше срока второго.
sort_order - сортировка выполненных заказов по срокам выполнения.
complete_orders - вектор выполненных заказов.
new_complete_orders - вектор номеров выполненных заказов, отсортированных по срокам выполнения.
make_schedule - создание расписания выполнения заказов.
deadlines - вектор сроков выполнения заказов.
fines - вектор штрафов за просрочку заказов.
number_orders - количество заказов.
overdue_orders - вектор номеров просроченных заказов.
orders!! - вектор заказов, отсортированных по штрафам.
num_order - текущий номер обрабатываемого заказа.
end_time - максимальный срок выполнения заказа плюс один.

class Order {
public:
    int deadline;
    int fine;
    int number;

    Order(int new_deadline, int new_fine, int new_number) {
        deadline = new_deadline;
        fine = new_fine;
        number = new_number;
    }
};

bool compare_for_fine(Order order_1, Order order_2) {
    return order_1.fine > order_2.fine;
}

vector<Order> init(vector<int> deadlines, 
                   vector<int> fines, int number_orders) {
    vector<Order> orders;
    for (int num_order = 0; num_order <  number_orders; num_order++) {
        Order order(deadlines[num_order], 
                    fines[num_order], num_order + 1);
        orders.push_back(order);
    }
    sort(orders.begin(), orders.end(), compare_for_fine);
    return orders;
}

bool compare_for_deadline(Order order_1, Order order_2) {
    return order_1.deadline < order_2.deadline;
}

vector<int> sort_order(vector<Order> complete_orders) {
    vector<int> new_complete_orders;
    sort(complete_orders.begin(), 
         complete_orders.end(), compare_for_deadline);
    for (Order order : complete_orders) {
        new_complete_orders.push_back(order.number);
    }
    return new_complete_orders;
}

vector<int> make_schedule(vector<int> deadlines, 
                          vector<int> fines, int  number_orders) {
    vector<int> overdue_orders, answer;
    vector<Order> complete_orders;
    vector<Order> orders = init(deadlines, fines, number_orders);
    int num_order = 0;
    int end_time = *max_element(deadlines.begin(), deadlines.end())+1;
    for (int time = 0; time < end_time; time++) {
        if (num_order < number_orders) {
            Order curr_order = orders[num_order];
            if (time <= curr_order.deadline) {
                complete_orders.push_back(curr_order);
            }
            else {
                overdue_orders.push_back(curr_order.number);
            }
            num_order += 1;
        }
    }
    vector<int> complete_orders = sort_order(complete_orders);
    answer.insert(answer.begin(), 
                  complete_orders.begin(), complete_orders.end());
    answer.insert(answer.end(), 
                  overdue_orders.begin(), overdue_orders.end());
    return answer;   
}