時間限制 1000 ms ・ 記憶體限制 64 MB
題目描述
一台印刷機要完成 N 個不可中斷的任務。任務 i 不能早於 sᵢ 開始，連續執行 tᵢ 單位時間後完成，且完成時刻不得晚於 dᵢ。同一時間只能執行一個任務。你可以自由決定任務順序與開始時間。找出最大的非負整數 G，使任意相鄰兩個任務之間都有至少 G 單位的閒置時間，並仍能完成全部任務。間隔等於後一任務開始時刻減去前一任務完成時刻。
輸入格式
第一行為 N，2 ≤ N ≤ 8。接下來 N 行各為 sᵢ、dᵢ、tᵢ，0 ≤ sᵢ < dᵢ ≤ 1000，1 ≤ tᵢ ≤ dᵢ−sᵢ。保證至少有一種可行排程。
輸出格式
輸出可達成的最大最短閒置間隔 G。
範例測資
範例輸入 1
3 1 9 3 3 20 4 4 15 2
範例輸出 1
5
範例輸入 2
3 1 4 2 0 6 3 2 8 1
範例輸出 2
0
請先登入後再提交程式碼
討論與題解
載入討論區…