NézetNyomtat

Staféta (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Mohó
Elmélet > Algoritmusok > Rendezések

Staféta

Az olimpiai lángot egy kiindulási városból a cél városba kell eljuttatni. A két város távolsága $K$ kilométer. Sok futó jelentkezett, mindegyikről tudjuk, hogy hányadik kilométertől hányadik kilométerig vállalja a futást. Ha egy futó az $x$ kilométertől az $y$ kilométerig vállalja a futást, akkor minden olyan futó át tudja venni tőle a lángot, aki olyan $z$ kilométertől vállalja a futást, hogy $x\leq z\leq y$.

Feladat

Írj programot (STAFETA.PAS, ...), amely kiszámítja, hogy legkevesebb hány futó kell ahhoz, hogy a láng eljusson a cél városig.

Bemenet

A STAFETA.BE szöveges állomány első sorában két egész szám található: a két város távolsága $(10\leq K\leq 1000)$ és a jelentkezett futók száma $(2\leq N\leq 20000)$. A további $N$ sor mindegyikében két egész szám van $I$ és $E$ ($0\leq I < E \leq K$) ami azt jelenti, hogy egy futó az $I$-edik kilométertől az $E$-edik kilométerig vállalja a láng továbbítását. A futókat a sorszámukkal azonosítjuk, a bemenet $j+1$-edik sorában a $j$-edik futó adata van. Feltételezhetjük, hogy a láng eljuttatható a cél városig a jelentkezett futókkal.

Kimenet

A STAFETA.KI szöveges állomány első sorába a láng célba juttatásához minimálisan szükséges futók $M$ számát kell írni. A második sor pontosan $M$ számot tartalmazzon (egy-egy szóközzel elválasztva), azon futók sorszámait, akik teljesítik a feladatot. Tehét a felsorolásban a $j$-edik futó a $j+1$-edik futónak adja át a lángot. Több megoldás esetén bármelyik megadható.

Példa



STAFETA.BESTAFETA.KI
40 7
2 21
25 35
20 34
0 10
5 18
3 7
34 40

4
4 1 3 7

Tesztadatok

stafeta.zip