E143. Оптимальный выбор заданий при известных временах завершения и длительностях выполнения

emaxx algorithm

#algorithm#emaxx#scheduling#sort

Task

Источник: e-maxx.ru/algo, страница PDF 474.

Пусть дан набор заданий, у каждого задания известен момент времени, к которому это задание нужно завершить, и длительность выполнения этого задания. Процесс выполнения какого-либо задания нельзя прерывать до его завершения. Требуется составить такое расписание, чтобы выполнить наибольшее число заданий.

Решение

Алгоритм решения — жадный (greedy). Отсортируем все задания по их крайнему сроку, и будем рассматривать их по очереди в порядке убывания крайнего срока. Также создадим очередь

, в которую мы будем постепенно

помещать задания, и извлекать из очереди задание с наименьшим временем выполнения (например, можно

использовать set или priority_queue). Изначально

пустая.

Пусть мы рассматриваем

-ое задание. Сначала поместим его в

. Рассмотрим отрезок времени между

сроком завершения

-го задания и сроком завершения

-го задания — это отрезок некоторой длины

Будем извлекать из

задания (в порядке увеличения оставшегося времени их выполнения) и помещать на выполнение

в этом отрезке, пока не заполним весь отрезок

. Важный момент — если в какой-то момент времени

очередное извлечённое из структуры задание можно успеть частично выполнить в отрезке

, то мы выполняем

это задание частично — именно настолько, насколько это возможно, т.е. в течение

единиц времени, а

оставшуюся часть задания помещаем обратно в

. По окончании этого алгоритма мы выберем оптимальное решение (или, по крайней мере, одно из нескольких

решений). Асимптотика решения —

Реализация

int n;

vector < pair<int,int> > a; // задания в виде пар (крайний срок, длительность)

... чтение n и a ...

sort (a.begin(), a.end());

typedef set < pair<int,int> > t_s;

t_s s;

vector<int> result;

for (int i=n-1; i>=0; --i) {

int t = a[i].first - (i ? a[i-1].first : 0);

s.insert (make_pair (a[i].second, i));

while (t && !s.empty()) {

t_s::iterator it = s.begin();

if (it->first <= t) {

t -= it->first;

result.push_back (it->second);

}

else {

s.insert (make_pair (it->first - t, it->second));

t = 0;

}

s.erase (it);

} }

for (size_t i=0; i<result.size(); ++i)

cout << result[i] << ' ';

C# solution

auto-draft, review before submit

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int n;
    vector < pair<int,int> > a; // задания в виде пар (крайний срок, длительность)
    ... чтение n и a ...
    sort (a.begin(), a.end());
    typedef set < pair<int,int> > t_s;
    t_s s;
    List<int> result;
    for (int i=n-1; i>=0; --i) {
            int t = a[i].first - (i ? a[i-1].first : 0);
            s.insert (make_pair (a[i].second, i));
            while (t && !s.empty()) {
                    t_s::iterator it = s.begin();
                    if (it->first <= t) {
                            t -= it->first;
                            result.push_back (it->second);
                    }
                    else {
                            s.insert (make_pair (it->first - t, it->second));
                            t = 0;
                    }
                    s.erase (it);
            }
    }
    for (size_t i=0; i<result.size(); ++i)
            Console.WriteLine( result[i] << ' ';
}

C++ solution

matched/original

int n;
vector < pair<int,int> > a; // задания в виде пар (крайний срок, длительность)
... чтение n и a ...
sort (a.begin(), a.end());
typedef set < pair<int,int> > t_s;
t_s s;
vector<int> result;
for (int i=n-1; i>=0; --i) {
        int t = a[i].first - (i ? a[i-1].first : 0);
        s.insert (make_pair (a[i].second, i));
        while (t && !s.empty()) {
                t_s::iterator it = s.begin();
                if (it->first <= t) {
                        t -= it->first;
                        result.push_back (it->second);
                }
                else {
                        s.insert (make_pair (it->first - t, it->second));
                        t = 0;
                }
                s.erase (it);
        }
}
for (size_t i=0; i<result.size(); ++i)
        cout << result[i] << ' ';

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int n;
    vector < pair<int,int> > a; // задания в виде пар (крайний срок, длительность)
    ... чтение n и a ...
    sort (a.begin(), a.end());
    typedef set < pair<int,int> > t_s;
    t_s s;
    ArrayList<Integer> result;
    for (int i=n-1; i>=0; --i) {
            int t = a[i].first - (i ? a[i-1].first : 0);
            s.insert (make_pair (a[i].second, i));
            while (t && !s.empty()) {
                    t_s::iterator it = s.begin();
                    if (it->first <= t) {
                            t -= it->first;
                            result.push_back (it->second);
                    }
                    else {
                            s.insert (make_pair (it->first - t, it->second));
                            t = 0;
                    }
                    s.erase (it);
            }
    }
    for (size_t i=0; i<result.size(); ++i)
            System.out.println( result[i] << ' ';
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.