CT32944

Forester and the Busy Hall

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Caravans arrive at the monsoon port of Rainhaven with crates of ribbons, and Forester the measurer 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 <= 1663; 0 <= s < e <= 10^9.

Example 1:

Input: 1019 337866393 337866410 35561049 35561060 598077988 598078000 630770268 630770332 662127382 662127448 978318792 978318817 259779228 259779285 865826389 865826444 871540322 871540382 749351135 749351142 806121096 806121146 214270550 214270629 501796787 501796868 813780889 813780974 118203204 118203235 548287085 548287179 491001188 491001259 932030652 932030717 277563907 277563973 254608051 254608117 983427026 983427055 253675896 253675959 416832073 416832094 880618526 880618600 11327992 11328012 912612731 912612782 379595770 379595833 143996432 143996438 905426969 905427036 246266845 246266873 882798422 882798508 976154768 976154804 214577893 214577985 851093567 851093643 438589737 438589746 265625934 265625954 508100841 508100864 546881915 546881956 257269158 257269208 388397750 388397752…
Output: 1

Example 2:

Input: 459 803010235 803010299 201287706 201287737 653245626 653245684 675456551 675456589 483526855 483526906 641549133 641549160 96999072 96999138 735682492 735682542 902186060 902186096 500523059 500523070 548855173 548855175 139739203 139739226 455718170 455718185 247108854 247108878 367480639 367480666 51042898 51042949 40117015 40117016 939394629 939394649 517939468 517939508 112466135 112466210 241850052 241850064 478675946 478675955 211524292 211524302 740714533 740714565 512869930 512869942 982026952 982026988 483776224 483776316 768836474 768836514 26369718 26369744 764847072 764847100 503513943 503513965 756469642 756469667 462204998 462205050 373453898 373453993 198868857 198868925 411961038 411961117 707645876 707645956 35020355 35020359 216921935 216921970 109819716 109819739 888708…
Output: 1

Example 3:

Input: 1170 965270710 965270754 176021523 176021555 539178802 539178842 252001651 252001658 631215182 631215211 661856157 661856246 404995359 404995412 634168986 634169032 744741782 744741827 688377129 688377207 370133893 370133993 952199095 952199182 427209221 427209308 251377657 251377688 262221017 262221106 49205361 49205368 611342008 611342078 349026446 349026486 465328737 465328785 560160898 560160986 273569340 273569424 13266997 13267097 376219405 376219413 60002509 60002600 334025195 334025265 10175791 10175809 862352347 862352384 542956816 542956865 801981670 801981674 916735397 916735426 686072431 686072446 173575664 173575711 256528664 256528748 201718039 201718076 593604699 593604739 885706756 885706851 428283465 428283529 970630763 970630804 479237946 479237983 451108363 451108381 175…
Output: 1

Constraints:

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

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