CT49187

The stretches at Deepwater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the fjord village of Deepwater opens only for a perfect tally of stretches. Hestia 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 <= 1903; 0 <= s < e <= 10^9.

Example 1:

Input: 134 621001557 621001634 633523018 633523030 614460748 614460825 99677363 99677396 253299166 253299256 882390392 882390436 559406589 559406660 981433085 981433103 311171401 311171491 965777469 965777560 451106996 451107090 53769358 53769395 690403718 690403744 204667560 204667605 833744593 833744639 178023117 178023119 385522346 385522362 481630991 481631060 896116665 896116756 108728142 108728234 825259151 825259214 149339996 149340076 707129231 707129252 30472359 30472411 472247847 472247901 581214643 581214666 766016554 766016600 637860401 637860447 876567870 876567953 793981266 793981307 619091774 619091798 242884447 242884517 735329461 735329527 426033748 426033833 152195178 152195194 708497255 708497354 889451497 889451514 399010669 399010701 134481431 134481516 776866385 776866456 49…
Output: 1

Example 2:

Input: 51 909797100 909797112 544727934 544727959 885594530 885594584 985662306 985662394 837016149 837016219 569647293 569647324 845487939 845487963 937847075 937847148 565673748 565673750 360293949 360294015 901980142 901980234 374369222 374369276 512316156 512316173 205926546 205926561 928469842 928469920 802568553 802568605 594721790 594721886 365041408 365041488 892772580 892772615 334418820 334418832 44101570 44101606 22124184 22124205 702965773 702965793 446151741 446151818 119336284 119336357 963048625 963048689 956136597 956136647 932028447 932028499 21482756 21482774 954665405 954665477 20898132 20898196 875819986 875820073 388992931 388992967 186027840 186027852 625088590 625088602 610531814 610531880 906092356 906092415 933219116 933219119 722893668 722893748 775719467 775719506 80817…
Output: 1

Example 3:

Input: 1863 476013988 476014062 213043358 213043375 636656296 636656326 582547299 582547365 553191025 553191118 286467705 286467757 496315702 496315718 967712258 967712261 211287056 211287077 23885409 23885424 436083988 436084086 221085585 221085606 7265984 7266065 398227387 398227453 280867522 280867548 213280986 213281073 95720021 95720087 376119429 376119464 226349706 226349801 822684849 822684895 6060353 6060414 830869469 830869533 2228176 2228202 496179618 496179689 589756563 589756579 726203310 726203395 877324190 877324263 467372827 467372874 529427312 529427377 978247283 978247325 781291293 781291367 949712082 949712120 266043230 266043281 215075001 215075075 326035973 326036073 300779490 300779520 496854368 496854369 851556904 851556995 737650612 737650681 672914170 672914174 940125361 9…
Output: 1

Constraints:

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

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