CT31821

Potter's Busy Hall Ledger

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the tulip beds of Bloomhaven opens only for a perfect tally of panels. Potter means to find out. Task: n crews each guard a half-open interval [s,e). An interval ending at time t does not overlap one starting at t. Print the maximum number overlapping at any instant. Input format: First line: n. Next n lines: s e. Output format: Print the maximum simultaneous overlap. Constraints: 1 <= n <= 1842; 0 <= s < e <= 10^9.

Example 1:

Input: 1305 896966785 896966839 645316996 645317023 816182856 816182907 281502671 281502750 157748171 157748185 19045131 19045151 128323616 128323641 581134422 581134458 681743109 681743166 829117802 829117823 818798098 818798171 290655417 290655465 736799953 736799978 962643775 962643802 427184308 427184335 140717740 140717807 425544164 425544216 819571553 819571561 883555224 883555286 247955126 247955156 341621739 341621804 534694776 534694852 460272308 460272333 73312198 73312226 915061724 915061801 883412779 883412792 374669050 374669076 9603159 9603244 653798091 653798137 230841446 230841527 161728507 161728516 932750512 932750536 580866866 580866880 160983445 160983475 516010707 516010719 518800000 518800045 585326289 585326377 992840082 992840110 461047687 461047717 348852460 348852525 685…
Output: 1

Example 2:

Input: 152 486686017 486686096 770549775 770549811 591317921 591317955 480368444 480368460 525529836 525529900 561342822 561342848 752476600 752476676 544360344 544360360 41323412 41323414 277528046 277528049 485409413 485409493 749281958 749281991 891703865 891703919 394591798 394591805 869307678 869307769 309989057 309989136 668885554 668885583 448763284 448763323 900167380 900167421 204903840 204903846 82105344 82105404 483761022 483761047 822445315 822445332 854884948 854884990 177725071 177725144 405496429 405496488 126576374 126576421 655972931 655972986 667099976 667100002 232088910 232088916 993197108 993197186 662730935 662731012 225962314 225962316 13267821 13267888 412722895 412722957 680374677 680374711 628979570 628979621 85953327 85953401 947367634 947367718 476277139 476277186 7125…
Output: 1

Example 3:

Input: 1367 735864466 735864565 620677442 620677520 991577891 991577899 22068220 22068293 661449816 661449867 833960284 833960347 834039455 834039470 29285400 29285447 268973311 268973348 493736528 493736544 114713430 114713503 538472841 538472891 441979142 441979211 556695081 556695126 168962962 168963038 123365085 123365179 714953381 714953396 267742170 267742181 569360537 569360592 706648336 706648408 308416768 308416786 770372544 770372559 279562266 279562304 783962106 783962182 383042253 383042313 927107497 927107539 843643983 843644079 481831073 481831123 424414833 424414897 150101466 150101562 884263347 884263392 907574311 907574330 304917980 304918038 748722146 748722233 276281556 276281584 955395479 955395556 447646628 447646723 746549655 746549735 176553654 176553754 684051861 684051865…
Output: 1

Constraints:

1 <= n <= 1842; 0 <= s < e <= 10^9.

Loading...
Test Cases:No test cases
No test cases available.