CT51187

Paige's Busy Hall Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the windmill fields of Gusthaven with crates of stretches, and Paige the quartermaster must account for every last one. 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 <= 2451; 0 <= s < e <= 10^9.

Example 1:

Input: 1194 510382346 510382384 820336602 820336689 437050143 437050151 142639563 142639619 59909906 59909948 359023251 359023347 645384818 645384893 515519612 515519658 523254716 523254802 645882081 645882107 273126705 273126732 671291435 671291438 78365458 78365501 32308536 32308574 667340863 667340891 149977225 149977297 861271200 861271297 910903873 910903877 2543064 2543078 649935610 649935611 147129814 147129897 314888822 314888847 105373956 105374048 180687666 180687755 366051443 366051474 93528422 93528461 509976818 509976821 679326820 679326854 680690272 680690332 37760987 37761085 895415808 895415839 258232553 258232644 226923016 226923101 689566082 689566123 498677302 498677313 241257520 241257603 289320279 289320342 351476833 351476893 85902053 85902079 641146772 641146797 369166938 3…
Output: 1

Example 2:

Input: 2226 381470513 381470560 957434060 957434127 43867811 43867830 23102533 23102564 271640371 271640385 17056778 17056783 248027394 248027426 446598295 446598369 844355620 844355668 145850915 145850959 20792906 20793005 12809718 12809768 957705044 957705136 185037837 185037871 336229721 336229766 437111559 437111634 432786887 432786937 567278959 567278966 491981531 491981614 627532999 627533088 881654664 881654754 964547581 964547596 308625146 308625160 406602562 406602569 530554429 530554492 886699493 886699529 305132751 305132757 395143261 395143272 969375044 969375119 656494649 656494661 700866729 700866783 540660660 540660687 532477910 532477990 822128221 822128228 521576199 521576201 253947205 253947226 862855625 862855677 364470791 364470798 707916432 707916528 362757994 362758005 85047…
Output: 2

Example 3:

Input: 595 948553254 948553316 163835295 163835320 366928154 366928193 616083034 616083107 501670058 501670116 97888156 97888202 3165469 3165472 392666890 392666971 629547501 629547589 885326393 885326476 837225186 837225214 559393153 559393219 260703300 260703336 131291775 131291792 946759056 946759105 474307919 474307970 514428730 514428807 520263428 520263521 892604605 892604642 109069973 109070060 429308785 429308871 281015891 281015957 620083310 620083328 23924656 23924720 370717932 370718009 590773149 590773169 25336370 25336402 810724209 810724234 903701451 903701482 664719310 664719376 433236265 433236347 309722413 309722437 387261195 387261271 199031449 199031517 41959121 41959176 980681442 980681474 580683676 580683758 775430499 775430528 81760187 81760277 943860145 943860181 666352207 …
Output: 1

Constraints:

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

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