GuilinDev

Lc1094

05 August 2008

1094 Car Pooling

当方向顺风车拼车

PQ

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

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        //排序，重写排序方法
        Arrays.sort(trips, Comparator.comparingInt(o -> o[1]));
        PriorityQueue<Message> pq = new PriorityQueue<>((x, y) -> x.end - y.end);
        //接上第一班人，并判断第一班人能不能全上车
        Message me = new Message(trips[0][0], trips[0][1], trips[0][2]);
        capacity -= me.quantity;
        if (capacity < 0) {
            return false;
        }
        pq.offer(me);
        //过站并判断
        for (int i = 1; i < trips.length; i++) {
            //当前站点信息储存
            Message m = new Message(trips[i][0], trips[i][1], trips[i][2]);
            //本站在上一站人的终点站之后后就是上一站的终点站，则先下车，空出车内空间
            //本站人上车，并用总容量减去本站人数
            if (m.start >= pq.peek().end) {
                while (!pq.isEmpty() && m.start >= pq.peek().end) {
                    Message p = pq.poll();
                    capacity += p.quantity;
                }
                pq.offer(m);
                capacity -= m.quantity;
            //本站在上一站的终点站前，只能直接上车
            } else {
                pq.offer(m);
                capacity -= m.quantity;
            }
            //若为负数，则超过本车容纳量，返回false
            if (capacity < 0) {
                return false;
            }
        }
        return true;
    }
}

class Message {
    int quantity;
    int start;
    int end;

    public Message(int quantity, int start, int end) {
        this.quantity = quantity;
        this.start = start;
        this.end = end;
    }
}

把一路上的负载数组构造出来，比较什么时候负载超重，就可以了

1
2
3
4
5
6
7
8
9
10
11
12

    public boolean carPooling(int[][] trips, int capacity) {
        int[] allTrip = new int[1001];
        for (int i = 0; i < trips.length; i++) {
            for (int j = trips[i][1]; j < trips[i][2]; j++) {
                allTrip[j] += trips[i][0];
                if (allTrip[j] > capacity) {
                    return false;
                }
            }
        }
        return true;
    }

直接记录上下车的容量变化情况，内存没变化，但是效率提升很快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    public boolean carPooling(int[][] trips, int capacity) {
        int[] capacityChanges = new int[1001];
        for (int i = 0; i < trips.length; i++) {
            capacityChanges[trips[i][1]] -= trips[i][0];
            capacityChanges[trips[i][2]] += trips[i][0];
        }

        for (int i = 0;i < capacityChanges.length;i++) {
            capacity += capacityChanges[i];
            if (capacity < 0) {
                return false;
            }
        }
        return true;
    }
This site is open source. Improve this page.