CT41855

The Will-o-Wisp Busy Hall

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Rohan found an old ledger of stretches in the ropewalk attic at the fen lights of Will-o-Wisp. The margin notes pose a precise question. 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 <= 1345; 0 <= s < e <= 10^9.

Example 1:

Input: 1302 854861413 854861486 769722963 769722970 124161811 124161830 448216395 448216396 386651607 386651634 204878478 204878537 108945367 108945446 906103000 906103017 446250498 446250552 199621871 199621956 313332541 313332564 680892016 680892060 97370803 97370853 22774822 22774886 177694829 177694882 354558718 354558769 882550979 882551004 486789636 486789730 96957364 96957416 120543717 120543751 840177819 840177904 53227552 53227597 692925893 692925973 824226757 824226823 664590488 664590523 815797164 815797217 215282391 215282473 222679064 222679148 225072296 225072382 498674192 498674234 907520776 907520838 92579162 92579210 255876671 255876759 383249067 383249074 487331078 487331176 569915181 569915213 368469112 368469178 205213519 205213618 222599983 222600016 317913592 317913654 66562…
Output: 2

Example 2:

Input: 99 266464837 266464890 247269549 247269590 506133039 506133110 473633782 473633838 61872586 61872595 775824660 775824729 987905492 987905575 422998086 422998094 151621882 151621969 338127538 338127617 222741643 222741661 586263753 586263800 386649750 386649825 179111824 179111839 962431221 962431224 913758695 913758780 955375739 955375742 338410608 338410624 923595489 923595587 361693540 361693580 951487969 951487977 241140012 241140106 651783888 651783962 849013495 849013522 172473555 172473567 319978083 319978145 628424392 628424468 855828934 855829020 831173390 831173436 710238499 710238559 800280356 800280370 809055390 809055445 399471059 399471090 551389031 551389064 402860429 402860512 597069915 597069950 900780189 900780221 141308147 141308208 419469192 419469268 699212054 699212114…
Output: 1

Example 3:

Input: 1188 906313221 906313309 3556790 3556810 311955671 311955683 981329159 981329227 445623704 445623793 401955929 401956000 828002037 828002086 155581192 155581199 690201839 690201882 570207319 570207411 832159376 832159423 333253705 333253794 460175820 460175845 323281121 323281144 690702597 690702634 531538057 531538093 461376922 461376958 45473103 45473157 694259926 694259932 542072059 542072115 951964884 951964975 326509454 326509523 979520954 979521034 199140824 199140917 945075260 945075360 483544468 483544542 695844261 695844275 503643948 503643957 47700705 47700711 23694846 23694899 602964869 602964915 309245096 309245160 87100967 87101021 838712409 838712467 531794225 531794272 649914450 649914504 78130388 78130415 105617540 105617548 103758036 103758048 532344453 532344527 848532071…
Output: 1

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Will-o-Wisp Busy Hall - MEDIUM Coding Problem | CodeTikki