予約、シフト、障害、販促は、どれも区間です:(start, end)の組です。ほとんどすべての区間の問題は、同じように始まります:始まりで並べ替えます。そうすれば、1回の走査で各区間を最後に残した区間と比べられます。
- 並べ替えた2つの区間は、次の始まりが現在の終わりより前のときに重なります。9-10と10-11のように接している区間を1つと数えるかどうかは、意図して決めてください。ここでは1つと数えます。
- まとめるときはリストを保ち、最後の区間を延ばすか、新しい区間を始めます。
- 空きは、まとめた区間の間の隙間です。
- 必要な部屋の数は、同時に開いている区間の最大数です:各区間を始まりでの+1のイベントと終わりでの-1のイベントにし、イベントを並べ替え、累計を追います。10:00に空いた部屋を10:00に再利用できるなら、同じ時刻では終わりを始まりより先に処理してください。
- 2つの予定の交わりは、2つのポインターで並べ替えた両方のリストをたどります。
このレッスンの時刻は、普通の数値で表した分や時間なので、ロジックが見えやすくなっています。