Programozás‎ > ‎Feladatok‎ > ‎

Párok

Egy rendezvényre sok vendéget hívtak meg. Minden vendég előre megadta, hogy mikor érkezik és mikor távozik. A rendezők fényképeken akarják megörökíteni a résztvevőket. Két feltételt kell teljesíteni:
  1. Minden képen pontosan két vendég legyen rajta.
  2. Minden vendég legfeljebb egy képen szerepelhet.
Természetesen két vendég csak akkor szerepelhet közös képen, ha van olyan F időpont, amikor mindketten jelen vannak. Egy vendég csak akkor van jelen egy F időpontban, ha E érkezési és T távozási idejére E<=F<T.

Feladat

Készíts programot, ami kiszámítja, hogy legjobb esetben hány fénykép készülhet, és megadja, hogy mely párok szerepelnek a fényképeken.

Bemenet

A bemenet első sora a vendégek számát adja meg (1<=N<30000), majd N sorban a vendégek érkezési és távozási ideje olvasható (1<=E<T<20000).

Kimenet

Az első sorba a fényképek maximális számát kell írni, utána pedig egy lehetséges megoldást: soronként egy párt, ahol a vendégeket sorszámukkal adjuk meg. 

Példa

Bemenet  Kimenet
8
1 3
2 5
2 3
8 10
2 4
4 7
5 8
7 8
3
1 3
5 2
6 7


Tesztadatok

Címkék

A feladat forrása: NTOITV 2011, 11-13. évfolyam, 3. forduló
Algoritmusok:

megoldás