CT41565

Wren's ribbons Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Wren runs the ferry office at the canyon post of Redrock. Today the books show a list of ribbons, and the numbers must be worked out before sundown. 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 <= 1946; 0 <= s < e <= 10^9.

Example 1:

Input: 301 632330282 632330285 431106589 431106605 923809303 923809339 510399715 510399739 488542118 488542190 325696179 325696250 251190605 251190665 33152867 33152929 555307338 555307393 675725123 675725182 345189056 345189064 88500817 88500835 576232811 576232855 557282452 557282459 880267339 880267385 167301233 167301274 499343696 499343745 853566968 853566980 624772442 624772524 400137744 400137745 727000735 727000760 327720150 327720215 354203709 354203789 815584480 815584520 215072144 215072146 969538922 969538938 813068882 813068924 823439086 823439112 713666351 713666392 458529762 458529805 844099975 844099993 132901361 132901404 544721744 544721821 442510746 442510820 516411557 516411589 84783437 84783490 325127656 325127733 253752856 253752882 652342178 652342230 126583632 126583661 32…
Output: 1

Example 2:

Input: 821 554550955 554550971 832916323 832916355 146557042 146557067 160281566 160281585 574144989 574145084 640019673 640019746 318397226 318397229 133316658 133316663 947007156 947007231 29524448 29524461 672367631 672367658 668967169 668967186 780835068 780835151 396447580 396447658 814015717 814015745 357130142 357130206 240930089 240930174 323392387 323392484 66739022 66739111 378117596 378117653 275487004 275487050 610749295 610749336 351445147 351445210 50549767 50549852 477013851 477013929 725091804 725091840 885850966 885850970 896015688 896015750 264856454 264856477 413572906 413572971 903024606 903024621 84814021 84814038 222997857 222997866 597642356 597642375 551719649 551719713 482556899 482556965 306993382 306993433 677080020 677080077 704571267 704571317 737753434 737753454 5740…
Output: 1

Example 3:

Input: 724 399424000 399424014 717927471 717927537 925465105 925465167 559891034 559891100 239122869 239122898 258520375 258520427 317071639 317071705 380846385 380846452 204607881 204607925 441837765 441837842 558833577 558833581 276147476 276147490 180098960 180099037 239985286 239985357 265714393 265714461 293378371 293378450 320886060 320886145 813128817 813128853 239829979 239830019 952781297 952781388 377793406 377793487 837882790 837882856 614597688 614597718 156888559 156888594 188379235 188379295 342392432 342392521 68923357 68923367 721820756 721820816 769715494 769715527 182963576 182963624 719502 719511 456417368 456417423 263272790 263272797 500932906 500933001 288430063 288430086 943208255 943208322 811712174 811712241 942899777 942899836 28775972 28775992 270047360 270047455 204285…
Output: 1

Constraints:

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

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