2023-07-07每日一題

一、題目編號

2532. 過橋的時間

二、題目鏈接

點擊跳轉(zhuǎn)到題目位置

三、題目描述

共有 k 位工人計劃將 n 個箱子從舊倉庫移動到新倉庫。給你兩個整數(shù) n 和 k，以及一個二維整數(shù)數(shù)組 time ，數(shù)組的大小為 k x 4 ，其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。

一條河將兩座倉庫分隔，只能通過一座橋通行。舊倉庫位于河的右岸，新倉庫在河的左岸。開始時，所有 k 位工人都在橋的左側(cè)等待。為了移動這些箱子，第 i 位工人（下標(biāo)從 0 開始）可以：

• 從左岸（新倉庫）跨過橋到右岸（舊倉庫），用時 leftToRighti 分鐘。
• 從舊倉庫選擇一個箱子，并返回到橋邊，用時 pickOldi 分鐘。不同工人可以同時搬起所選的箱子。
• 從右岸（舊倉庫）跨過橋到左岸（新倉庫），用時 rightToLefti 分鐘。
• 將箱子放入新倉庫，并返回到橋邊，用時 putNewi 分鐘。不同工人可以同時放下所選的箱子。

如果滿足下面任一條件，則認(rèn)為工人 i 的 效率低于 工人 j ：

• leftToRighti + rightToLefti > leftToRightj + rightToLeftj
• leftToRighti + rightToLefti == leftToRightj + rightToLeftj 且 i > j

工人通過橋時需要遵循以下規(guī)則：

• 如果工人 x 到達(dá)橋邊時，工人 y 正在過橋，那么工人 x 需要在橋邊等待。
• 如果沒有正在過橋的工人，那么在橋右邊等待的工人可以先過橋。如果同時有多個工人在右邊等待，那么 效率最低 的工人會先過橋。
• 如果沒有正在過橋的工人，且橋右邊也沒有在等待的工人，同時舊倉庫還剩下至少一個箱子需要搬運，此時在橋左邊的工人可以過橋。如果同時有多個工人在左邊等待，那么 效率最低 的工人會先過橋。

所有 n 個盒子都需要放入新倉庫，請你返回最后一個搬運箱子的工人 到達(dá)河左岸 的時間。

提示：

• 1 <= n, k <= 10⁴
• time.length == k
• time[i].length == 4
• 1 <= leftToRighti, pickOldi, rightToLefti, putNewi <= 1000

四、解題代碼

/*
    time[i][0] : leftToRight
    time[i][1] : pickOld
    time[i][2] : rightToLeft
    time[i][3] : putNew
*/

class Solution {
public:
    using p = pair<int, int>;
    int findCrossingTime(int n, int k, vector<vector<int>>& time) {
        auto wait_priority_cmp = [&](int x, int y) {
            int time_x = time[x][0] + time[x][2];
            int time_y = time[y][0] + time[y][2];
            return time_x != time_y ? time_x < time_y : x < y;
        };
        /*
        優(yōu)先隊列1 左右等待
        */
        priority_queue<int, vector<int>, decltype(wait_priority_cmp)> wait_left(wait_priority_cmp),
    wait_right(wait_priority_cmp);
        /*
        優(yōu)先隊列2 左右工作
        */

        priority_queue<p, vector<p>, greater<p>> work_left, work_right;

        int remain_box = n, cur_time = 0;
        for(int i = 0; i < k; ++i){
            wait_left.push(i);
        }
        while(remain_box > 0 || !work_right.empty() || !wait_right.empty()){
            while (!work_left.empty() && work_left.top().first <= cur_time) {
                wait_left.push(work_left.top().second);
                work_left.pop();
            }
            
            while (!work_right.empty() && work_right.top().first <= cur_time) {
                wait_right.push(work_right.top().second);
                work_right.pop();
            }

            if (!wait_right.empty()) {
                // 2. 若右側(cè)有工人在等待，則取出優(yōu)先級最低的工人并過橋
                int id = wait_right.top();
                wait_right.pop();
                cur_time += time[id][2];
                work_left.push({cur_time + time[id][3], id});
            } else if (remain_box > 0 && !wait_left.empty()) {
                // 3. 若右側(cè)還有箱子，并且左側(cè)有工人在等待，則取出優(yōu)先級最低的工人并過橋
                int id = wait_left.top();
                wait_left.pop();
                cur_time += time[id][0];
                work_right.push({cur_time + time[id][1], id});
                remain_box--;
            } else {
                // 4. 否則，沒有人需要過橋，時間過渡到 work_left 和 work_right 中的最早完成時間
                int next_time = INT_MAX;
                if (!work_left.empty()) {
                    next_time = min(next_time, work_left.top().first);
                }
                if (!work_right.empty()) {
                    next_time = min(next_time, work_right.top().first);
                }
                if (next_time != INT_MAX) {
                    cur_time = max(next_time, cur_time);
                }
            }
        }
        return cur_time;
    }
};

五、解題思路

(1) 采用優(yōu)先隊列進(jìn)行模擬。文章來源地址http://www.zghlxwxcb.cn/news/detail-555870.html

到了這里，關(guān)于2023-07-07 LeetCode每日一題（過橋的時間）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！