Hide

Mötet

En styrelse med $N$ medlemmar planerar att ha ett möte. På grund av det stora antalet styrelseledamöter är det svårt att hitta en tid som passar alla, men man vill gärna att så många personer som möjligt kan vara med på mötet.

Varje ledamot är tillgänglig under ett antal olika tidsintervall, där varje tidsintervall $[a, b]$ betyder att ledamöten kan närvara om mötet startar vid någon tid $t$ där $a \le t \le b$. Eftersom vissa ledamöter är väldigt slarviga med sina kalendrar kan en och samma ledamot råka ge dig olika tidsintervall som överlappar, t.ex $[1, 3]$ och $[2, 4]$, även om det haed räckt med ett enda intervall, i detta fall $[1, 4]$.

Beräkna det största antalet ledamöter som kan delta på mötet.

Indata

Den första raden innehåller ett heltal $N$ ($1 \le N \leq 2\cdot 10^5$), antalet ledamöter i styrelsen.

Därefter följer $N$ rader, en för varje styrelseledamot. Den $i$:te raden börjar med antalet tidsintervall $m_ i$ ($1 \leq m_ i \leq 2\cdot 10^5$) som den $i$:te ledamöten kan närvara under. Detta följs av $m_ i$ par av heltal, ett för varje intervall. Dessa par $a, b$ ($0 \le a \le b \le 10^9$) representerar intervallet $[a, b]$.

Låt $B=\sum _{i=1}^{N} m_ i$ vara summan av antalet tidsintervall som alla ledamöter är tillgängliga under. Då gäller det att $B \leq 2\cdot 10^5$.

Utdata

Skriv ut en rad med ett heltal – det största antalet ledamöter som kan delta i mötet om starttiden väljs optimalt.

Poängsättning

Din lösning kommer att testas på en antal testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$10$

$B \leq 100$ och $0 \leq a \leq b \leq 100$

$2$

$15$

$B \leq 1\, 000$, och $0 \leq a \leq b \leq 4\, 000$, och ingen enskild ledamot har två tidsintervall som överlappar

$3$

$30$

Ingen enskild ledamot har två tidsintervall som överlappar

$4$

$15$

$B \leq 1\, 000$ och $0 \leq a \leq b \leq 4\, 000$

$5$

$30$

Inga ytterligare begränsningar

Notera att vissa exempelfall är inte giltiga i alla testfallsgrupper.

Förklaring av exempelfall

I det första exemplet kan vi välja att starta mötet vid tiden $4$, då ledamot $2$ och $3$ kan delta. Fallet skulle kunna vara med i samtliga testfallsgrupper.

Exempel $2$ och $3$ skulle inte kunna förekomma i testfallsgrupp $2$ eller $3$.

Sample Input 1 Sample Output 1
3
2 1 3 5 6
4 1 10 11 12 17 18 14 15
1 4 4
2
Sample Input 2 Sample Output 2
3
3 2 8 2 7 5 6
4 7 15 15 20 9 13 18 20
3 12 19 9 16 12 16
2
Sample Input 3 Sample Output 3
3
2 5 14 0 20
3 5 16 5 11 8 9
2 7 11 7 18
3
CPU Time limit 6 seconds
Memory limit 1024 MB
Author
Abdullah Zaghmout
Source Programmeringsolympiadens onlinekval 2022
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in