Blage's Coding
phan
2023-07-07
目录

2532. 过桥的时间

# 2532. 过桥的时间 (opens new window)

# 1.😭😭😭第一遍超时

  • 用四个优先级队列保存每个工人存在四种状态：
    • 左边等待
    • 左边搬运
    • 右边等待
    • 右边搬运
  • 每个工人存在两种行为：
    • 过桥。按照题意只能串行过桥，并且右边的先过桥，才轮到左边
    • 搬运。搬运行为是并行的，也就是说其它工人在过桥或者是搬运时，当前工人的搬运行为不受影响。

题目的难点在于如何统计总时长？这里采用的算法是根据过桥时间来统计，因为整个过桥行为都是串行的，所以可以把每个工人的过桥行为作为时间主轴。如果当前不存在“可过桥”工人，那么就取出最快完成搬运任务的工人再过桥。

搬运行为是并行的，因此每过一次桥就扣减一次所有执行搬运任务工人的时长，根据搬运时长是否小于零决定将当前工人纳入等待队列。而这也是超时的主要原因。

class Solution {
    public  int findCrossingTime(int n, int k, int[][] time) {
        PriorityQueue<int[]> rightwork = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1] ;
            }
        });
        PriorityQueue<int[]> rightwait = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0] ;
            }
        });
        PriorityQueue<int[]> leftwork = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1] ;
            }
        });
        PriorityQueue<int[]> leftwait = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0] ;
            }
        });
        Deque<int[]> temp = new LinkedList<>();
        Arrays.sort(time, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0] + o1[2] - o2[0] - o2[2];
            }
        });
        for (int i = time.length - 1; i >= 0; i--) {
            leftwait.offer(new int[]{i,time[i][0]});
        }

        int index = time.length - 1, res = 0, box = 0;
        while (box < n) {
            //右边先过桥
            if (rightwait.size()>0) {
                int[] worker = rightwait.poll();
                //过桥时间
                int rightToleftTime = worker[1];
                res += rightToleftTime;
                //缩减左右两边工作时间
                refresh(leftwork,leftwait,temp,time,leftwork.size(),rightToleftTime,0);
                refresh(rightwork,rightwait,temp,time,rightwork.size(),rightToleftTime,2);
                leftwork.offer(new int[]{worker[0], time[worker[0]][3]});
            }
            //左边过桥
            else if(rightwait.size() == 0&&leftwait.size()>0){
                int[] worker = leftwait.poll();
                //过桥时间
                int lefttorightTime = worker[1];
                res += lefttorightTime;
                //缩减左右两边工作时间
                refresh(leftwork,leftwait,temp,time,leftwork.size(),lefttorightTime,0);
                refresh(rightwork,rightwait,temp,time,rightwork.size(),lefttorightTime,2);
                rightwork.offer(new int[]{worker[0], time[worker[0]][1]});
                box++;
            }
            //左右两边没有空闲worker，同时都在工作，则取出最快完成搬运工作的worker
            else if (rightwait.size() == 0 && leftwait.size() == 0) {
                int timeing=0;
                if(rightwork.size()!=0&&leftwork.size()!=0&&rightwork.peek()[1]==leftwork.peek()[1]){
                    //同时完成
                    int[] poll=leftwork.poll();
                    timeing = poll[1];
                    leftwait.offer(new int[]{poll[0], time[poll[0]][0]});
                    poll=rightwork.poll();
                    rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                }
                else{
                    if(!rightwork.isEmpty()&&!leftwork.isEmpty()){
                        if (rightwork.peek()[1] > leftwork.peek()[1]) {
                            int[] poll = leftwork.poll();
                            leftwait.offer(new int[]{poll[0], time[poll[0]][0]});
                            timeing = poll[1];
                        }
                        else{
                            int[] poll = rightwork.poll();
                            rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                            timeing = poll[1];
                        }
                    }
                    else {
                        if(rightwork.isEmpty()){
                            int[] poll = leftwork.poll();
                            leftwait.offer(new int[]{poll[0], time[poll[0]][0]});
                            timeing = poll[1];

                        }
                        else{
                            int[] poll = rightwork.poll();
                            rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                            timeing = poll[1];
                        }
                    }
                }
                res += timeing;
                refresh(leftwork,leftwait,temp,time,leftwork.size(),timeing,0);
                refresh(rightwork,rightwait,temp,time,rightwork.size(),timeing,2);
            }
        }
        //最后处理右边
        while(rightwork.size()>0||rightwait.size()>0){
            //过桥
            if(rightwait.size()>0){
                int[] poll = rightwait.poll();
                res += poll[1];
                refresh(rightwork,rightwait,temp,time,rightwork.size(),poll[1],2);
            }
            //右边搬运
            else{
                int[] poll = rightwork.poll();
                res += poll[1];
                rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                refresh(rightwork,rightwait,temp,time,rightwork.size(),poll[1],2);
            }
        }

        return res;
    }
    //刷新工作队列所有worker的剩余搬运时间
    public  void refresh(PriorityQueue<int[]> work,PriorityQueue<int[]> wait,Deque<int[]> temp,int[][] time,int len,int crosstime,int refreshinx){
        int lworkinx = 0;
        while (lworkinx<len) {
            int[] worker = work.poll();
            //过桥期间做完的
            if (worker[1]<=crosstime) {
                wait.offer(new int[]{worker[0],time[worker[0]][refreshinx]});
            }
            //没做完的重新加入队列
            else{
                worker[1] -= crosstime;
                temp.offer(worker);
            }
            lworkinx++;
            if(lworkinx==len){
                while (temp.size() > 0) {
                    work.offer(temp.poll());
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

# 2.优化

优化：搬运队列直接保存完成该搬运任务的"时刻"，而不是时间间隔。

上一种方法里，搬运队列保存的是完成整个搬运任务所需要的时间(pickNew/putOld)，也就是时间间隔。因此每经过一段过桥时长，所有的搬运任务都需要refresh刷新扣减，否则无法判断每个并行的搬运任务完成并加入等待队列的时机。

而优化过后，整个过桥逻辑如下：

  1. 先过桥，并更新记录当前完成过桥到达对岸的时刻res
    • 过桥后的工人纳入对岸搬运任务队列，他完成这个搬运任务的时刻应该等于res(到达对岸的时刻)+pickNew(做完这个搬运任务的时间间隔)。
  2. 统计过桥期间完成搬运任务纳入等待队列的工人：
    • res大于搬运任务队列的时刻，说明这个搬运任务在过桥期间做完了，将它纳入等待队列。

如果当前左右两岸的等待队列都没人，不存在过桥条件，那么需要等待最快的工人搬完，并将下一次过桥前的时刻res更新为完成搬运任务的时刻。

预处理步骤：

  • 首先对time排序，保证索引大的工人效率低。
  • 搬运队列leftwork和rightwork比较器按照完成搬运时刻升序排序。等待队列leftwait和rightwait比较器按照time的工人索引下标降序排序。
  • 队列需要保存索引index。从而保证工人状态切换时，可以根据索引从time中获取数据。
class Solution {
    public int findCrossingTime(int n, int k, int[][] time) {
        PriorityQueue<int[]> rightwork = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1] ;
            }
        });
        PriorityQueue<int[]> rightwait = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0] ;
            }
        });
        PriorityQueue<int[]> leftwork = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1] ;
            }
        });
        PriorityQueue<int[]> leftwait = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0] ;
            }
        });
        Deque<int[]> temp = new LinkedList<>();
        Arrays.sort(time, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0] + o1[2] - o2[0] - o2[2];
            }
        });
        for (int i = time.length - 1; i >= 0; i--) {
            leftwait.offer(new int[]{i,time[i][0]});
        }
        int res = 0, box = 0;
        while (box < n) {
           //右往左
            if (rightwait.size() > 0) {
                int[] toLeft = rightwait.poll();
                res += toLeft[1];
                //将工人从搬运队列添加到等待队列
                while(leftwork.size()>0&&leftwork.peek()[1]<=res){
                    int[] poll = leftwork.poll();
                    leftwait.offer(new int[]{poll[0], time[poll[0]][0]});
                }
                while(rightwork.size()>0&&rightwork.peek()[1]<=res){
                    int[] poll = rightwork.poll();
                    rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                }
                leftwork.offer(new int[]{toLeft[0], res + time[toLeft[0]][3]});
            }
            //左往右
            else if (rightwait.size() == 0 && leftwait.size() > 0) {
                int[] tiright = leftwait.poll();
                res += tiright[1];
                //将工人从搬运队列添加到等待队列
                while(leftwork.size()>0&&leftwork.peek()[1]<=res){
                    int[] poll = leftwork.poll();
                    leftwait.offer(new int[]{poll[0], time[poll[0]][0]});
                }
                while(rightwork.size()>0&&rightwork.peek()[1]<=res){
                    int[] poll = rightwork.poll();
                    rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                }
                rightwork.offer(new int[]{tiright[0], res + time[tiright[0]][1]});
                box++;
            }
            //两边都没有等待队列，取出最快完成搬运任务的工人
            else {
                if(leftwork.size()==0){
                    int[] poll = rightwork.poll();
                    res = poll[1];
                    rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                } else if (rightwork.size() == 0) {
                    int[] poll = leftwork.poll();
                    res = poll[1];
                    leftwait.offer(new int[]{poll[0], time[poll[0]][0]});
                }
                else{
                    if(leftwork.peek()[1]<rightwork.peek()[1]){
                        int[] poll = leftwork.poll();
                        res = poll[1];
                        leftwait.offer(new int[]{poll[0], time[poll[0]][0]});
                    } else if (leftwork.peek()[1] > rightwork.peek()[1]) {
                        int[] poll = rightwork.poll();
                        res = poll[1];
                        rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                    }
                    //左右两边搬运工人同时出栈
                    else{
                        int[] poll = leftwork.poll();
                        res = poll[1];
                        leftwait.offer(new int[]{poll[0], time[poll[0]][0]});
                        poll=rightwork.poll();
                        rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
                    }
                }
            }
        }
        //第n个工人到右岸后，处理剩余右岸的搬运任务
        while(rightwork.size()>0||rightwait.size()>0){
            //右边有人等待
            if (rightwait.size() > 0) {
                int[] poll = rightwait.poll();
                res += poll[1];
                while(rightwork.size()>0&&rightwork.peek()[1]<=res){
                    int[] out = rightwork.poll();
                    rightwait.offer(new int[]{out[0], time[out[0]][2]});
                }
            }
            //右边没人等，则取出最先搬完活的工人
            else{
                int[] poll = rightwork.poll();
                res = poll[1];
                rightwait.offer(new int[]{poll[0], time[poll[0]][2]});
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
编辑 (opens new window)
#Leetcode#模拟
上次更新: 2023/12/15, 15:49:57
1253. 重构 2 行二进制矩阵
874. 模拟行走机器人

← 874. 模拟行走机器人→

Theme by Vdoing | Copyright © 2023-2024 blageCoder