Hogyan lehet ezt a feladatot megoldani?

4. feladat: Beruházás (40 pont)

Egy nagyszabású beruházás terve N különböző munka elvégzését írja elő. Minden munkát pontosan egy nap alatt lehet elvégezni, azonban minden munkára elő van írva az a határidő, ameddig el kell végezni. A beruházó a munkák elvégzésére alvállalkozókat szerződtet. Minden alvállalkozó bármely munkát el tudja végezni, de egy nap csak egy munkát tud végezni.

Készíts programot, amely megadja, hogy legkevesebb hány alvállalkozót kell szerződtetni, hogy minden munkát határidőre elvégezzék! A munkák egy ütemezését is meg kell adni.

A standard bemenet első sorában az elvégzendő munkák száma van (2≤N≤10000). A további N sor mindegyike egy munka határidejét tartalmazza (1≤Hi≤300).

A standard kimenet első sorába a legkevesebb alvállalkozók K számát kell írni, amennyivel minden munka elvégezhető határidőre! A következő N sor a munkák egy lehetséges beosztását tartalmazza! Az első szám a sorban egy munka (1 és N közötti) sorszáma, a második a munkát elvégző vállalkozó (1 és K közötti) sorszáma, a harmadik pedig annak a napnak a sorszáma legyen, amikor a munkát elvégzi a vállalkozó! Több megoldás esetén bármelyik megadható.

Példa:

bemenet kimenet

7 3

1 1 1 1

2 2 1 2

1 3 2 1

3 4 3 2

2 5 2 2

2 6 3 1

3 7 1 3

Ezzel a feladattal már nagyon sokat foglalkoztam, és nem sikerül megoldani.

A válaszokat előre is köszönöm!