CT39961

The Busy Hall of the Celestial windows

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Lothar the dispatch writer watches over the mining town of Ironvein's stores of windows. A careful computation stands between order and chaos. 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 <= 1538; 0 <= s < e <= 10^9.

Example 1:

Input: 1322 362299433 362299442 116708353 116708375 395126023 395126061 643019697 643019703 90696089 90696094 296540073 296540117 426569429 426569443 378689115 378689213 596116910 596116927 860663446 860663482 47688465 47688471 547860663 547860688 876087177 876087262 209823567 209823599 751461683 751461697 935129306 935129381 419377488 419377497 550930187 550930203 219879710 219879794 59588623 59588674 302713239 302713242 52108671 52108733 705309983 705310060 744837397 744837474 768088106 768088202 89449719 89449817 126057652 126057671 249074719 249074751 752338958 752338972 833051728 833051823 60607199 60607290 232244649 232244730 657573806 657573891 467037733 467037818 421494113 421494191 622407528 622407557 507100454 507100533 879488673 879488693 295164121 295164128 244256897 244256997 4670745…
Output: 2

Example 2:

Input: 1335 716774274 716774276 796347922 796347994 626311164 626311198 774722603 774722631 402994140 402994201 227084871 227084894 59720067 59720068 634285276 634285348 814115561 814115607 173048306 173048343 325561256 325561345 172947370 172947420 181726640 181726734 629234337 629234412 787728925 787729016 986742148 986742164 234998369 234998447 317566908 317566986 478406410 478406439 533457072 533457073 547586707 547586715 350917274 350917297 224912798 224912818 525132881 525132981 36603038 36603120 617734896 617734968 547331328 547331368 837602739 837602759 5920486 5920529 572180049 572180050 470319132 470319166 379977173 379977256 38559991 38560088 426224310 426224339 847631320 847631418 84138571 84138605 379563492 379563557 105476703 105476705 864222135 864222188 484116007 484116075 9496821…
Output: 1

Example 3:

Input: 456 540939554 540939578 30665221 30665228 73193093 73193163 689391103 689391203 827286859 827286895 781351900 781351947 619753096 619753168 700445829 700445908 766020109 766020155 496050697 496050718 700147849 700147946 934537044 934537102 244342575 244342644 107617552 107617569 578489037 578489134 223901343 223901358 98078059 98078095 325037611 325037663 410243684 410243780 437031237 437031282 803440217 803440290 783161551 783161577 791189874 791189933 651703892 651703991 114379380 114379396 737962173 737962254 153032453 153032460 584831932 584831959 768854752 768854807 602512430 602512517 213986156 213986233 814031557 814031629 246956102 246956124 749748145 749748240 870950714 870950775 575186400 575186482 792928577 792928599 913402274 913402300 702762522 702762591 19910241 19910272 3796…
Output: 1

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Busy Hall of the Celestial windows - MEDIUM Coding Problem | CodeTikki