Job Sequencing Problem

Q: Jaka jest złożoność czasowa problemu szeregowania zadań?

Dla zbioru rozłącznego złożoność czasowa wynosi O(n log n) , a dominuje sortowanie; złożoność pamięciowa to O(n) . Przeszukiwanie wstecz od każdego terminu w poszukiwaniu wolnego miejsca kosztuje O(n²) , gdy większość terminów jest odległa.

ŚrednieAlgorytmy zachłanne Sortowanie

+10

Otrzymujesz n zadań w postaci dwóch tablic: zadanie i przynosi zysk profit[i], jeśli zostanie ukończone do czasu deadline[i]. Każde zadanie trwa jedną jednostkę czasu, wykonujesz jedno zadanie naraz, zaczynając w chwili 0, i możesz pominąć dowolne zadanie. Zadanie z terminem 2 można wykonać od 0 do 1 lub od 1 do 2.

Zwróć największy łączny zysk, jaki możesz osiągnąć.

Funkcja

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: czas, do którego każde zadanie musi zostać ukończone, od 1 do n
profitinteger-array: ile zarabia każda praca; profit[i] odpowiada deadline[i]
Zwracainteger: największy łączny zysk z zadań, które można ukończyć przed upływem ich terminów

Ograniczenia

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, gdzie n to liczba zadań
1 ≤ profit[i] ≤ 10⁵
Tablice nie są posortowane. Kilka zadań może mieć ten sam termin lub zysk.

Przykłady

Wejście: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Wyjście: 120
Wyjaśnienie: Mieści się tylko jedno z dwóch zadań z terminem 1, więc wykonaj to warte 50. Zadanie warte 30 kończy się wtedy w terminie 2, a zadanie warte 40 w terminie 3: 50 + 30 + 40 = 120.

Wejście: deadline = [1, 1, 1]profit = [5, 9, 7]
Wyjście: 9
Wyjaśnienie: Wszystkie trzy zadania muszą zakończyć się przed czasem 1, a przedtem zmieści się tylko jedno zadanie. Najlepsze z nich przynosi 9.

Pytanie dodatkowe

Co jeśli zadanie i trwa duration[i] jednostek czasu zamiast jednej? Czy rozpoczęcie od najbardziej opłacalnego zadania nadal daje najlepszy wynik łączny?

Rozwiązanie

Wybierasz, które zadania zachować i kiedy je uruchomić. Jedna zachłanna reguła rozstrzyga obie kwestie: bierz zadania od najbardziej opłacalnego do najmniej opłacalnego i umieszczaj każde w najpóźniejszym wolnym przedziale czasowym w terminie lub przed nim; pomiń je, jeśli żaden nie jest wolny. Zbiór rozłączny znajduje ten przedział bez przechodzenia przez już zajęte.

Zachłanne podejście według zysku, wyszukiwanie wolnego przedziału

Intuicja

Podziel czas na przedziały: przedział t trwa od t-1 do t, zadanie z terminem d może wykorzystać przedziały od 1 do d, a żaden termin nie przekracza n. Wybieranie najpierw najbardziej dochodowego zadania jest bezpieczne: jeśli wszystkie przedziały, których może ono użyć, są zajęte, zamiana go na zadanie zaplanowane w jednym z nich przynosi co najmniej taki sam zysk. Bezpieczne jest rezerwowanie najpóźniejszego przedziału, ponieważ tylko wczesne przedziały mogą być wykorzystane przez zadania z krótkim terminem.

Kosztem jest przeszukiwanie. Gdy każdy termin wynosi n, k-te zadanie musi przejść przez k-1 zarezerwowanych przedziałów: około n²/2, czyli 12,5 miliona kroków dla n = 5000.

Algorytm

Posortuj zadania według zysku, zaczynając od największego, zachowując termin każdego zadania wraz z jego zyskiem.
Utwórz tablicę taken składającą się z n + 1 flag, wszystkie ustawione na false.
Dla każdego zadania odliczaj t od jego terminu do 1 i zatrzymaj się na pierwszym zajętym slocie.
Jeśli znajdziesz taki slot, oznacz go jako zajęty i dodaj zysk z zadania do total.
Zwróć total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

Algorytm zachłanny oparty na zysku z użyciem struktury rozłącznych zbiorów wolnych terminów

Intuicja

Skanowanie wielokrotnie przechodzi po tych samych zajętych przedziałach czasowych. Zbiór rozłączny dla przedziałów od 0 do n pozwala je pomijać: parent[t] = t, gdy przedział t jest wolny, a jego zarezerwowanie ustawia parent[t] = t-1, więc podążanie za wskaźnikami od terminu prowadzi do najpóźniejszego wolnego przedziału. Dotarcie do przedziału 0 oznacza, że nic już nie zostało. Spłaszczanie ścieżki przesuwa każdy mijany wskaźnik o dwa kroki naprzód, dzięki czemu kolejne przejścia są krótsze.

W trzecim przykładzie zadania warte 60 i 50 zajmują przedziały 2 i 1. Zadanie warte 20, z terminem 2, podąża od 2 do 1, a następnie do 0, więc zostaje pominięte.

Sortowanie kosztuje O(n log n), a przy spłaszczaniu ścieżki każde wyszukiwanie kosztuje zamortyzowane O(log n), więc łączny koszt pozostaje równy O(n log n).

Algorytm

Posortuj zadania według zysku, od największego do najmniejszego, zachowując przypisany do każdego zysku termin.
Ustaw parent[t] = t dla każdego przedziału t od 0 do n.
Dla każdego zadania zacznij od slot = deadline i podążaj za parent, aż parent[slot] == slot, po drodze skracając ścieżkę o połowę.
Jeśli slot > 0, dodaj zysk z zadania i ustaw parent[slot] = slot-1; w przeciwnym razie pomiń zadanie.
Zwróć sumę.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

Pułapki i przypadki brzegowe

Umieszczanie zadania w najwcześniejszym wolnym slocie. W trzecim przykładzie zadanie warte 60 zajęłoby slot 1, a zadanie warte 50 zostałoby utracone: 80 zamiast 110.
Wybieranie zadań według terminu. Przy terminach [1, 1] i zyskach [1, 100] tanie zadanie zajmuje jedyny slot i zarabiasz 1 zamiast 100.
Ustawienie rozmiaru tablicy slotów na n zamiast n + 1. Termin równy n spowoduje wtedy odczyt poza końcem tablicy.
Sortowanie samych zysków. Każdy termin musi przesuwać się razem ze swoim zyskiem.
Zapisanie kroku wyszukiwania z użyciem rekurencji. Łańcuch przechodzący przez tysiące zajętych slotów może przepełnić stos; użyj pętli.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu szeregowania zadań?

Dla zbioru rozłącznego złożoność czasowa wynosi O(n log n), a dominuje sortowanie; złożoność pamięciowa to O(n). Przeszukiwanie wstecz od każdego terminu w poszukiwaniu wolnego miejsca kosztuje O(n²), gdy większość terminów jest odległa.

Dlaczego zachłanne podejście działa w przypadku szeregowania zadań?

Niektóre najlepsze harmonogramy zawierają najbardziej opłacalne zadanie. Jeśli zostanie ono pominięte, a przed jego terminem będzie wolny przedział, dodanie go przyniesie większy zysk; jeśli wszystkie takie przedziały będą zajęte, zastąpienie nim innego zadania przyniesie co najmniej taki sam zysk. Ten argument powtarza się dla pozostałych zadań.

Czy problem szeregowania zadań można rozwiązać za pomocą kopca?

Tak. Posortuj zadania według terminu i dodawaj każdy zysk do kopca minimum. Gdy w kopcu znajdzie się więcej zadań, niż pozwala na to bieżący termin, usuń najmniejszy zysk. Na końcu kopiec zawiera najlepszy zestaw zadań, a jego suma jest odpowiedzią, w czasie O(n log n).

def jobSequencing(deadline, profit):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argumenty

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

Oczekiwany wynik