algorithm/leetcode/QueueReconstructionByHeight.java at master · skyczhao/algorithm · GitHub

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
package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * QueueReconstructionByHeight
 * https://leetcode-cn.com/problems/queue-reconstruction-by-height/
 * 406. 根据身高重建队列
 *
 * @since 2020-11-16
 */
public class QueueReconstructionByHeight {
    public static void main(String[] args) {
        int[][] people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};

        QueueReconstructionByHeight sol = new QueueReconstructionByHeight();
        int[][] res = sol.reconstructQueue(people);
        for (int[] p : res) {
            System.out.println(p[0] + ", " + p[1]);
        }
    }


    public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length < 1) {
            return people;
        }

        List<int[]> result = new LinkedList<>();
        List<int[]> origin = new ArrayList<>();
        for (int[] person : people) {
            origin.add(new int[]{person[0], person[1]});
        }
        boolean[] flags = new boolean[people.length];
        for (int idx = 0; idx < people.length; idx++) {
            flags[idx] = true;
        }

        int minIdx = 0;
        boolean isChange = false;
        while (true) {
            isChange = false;
            minIdx = 0;
            int[] minValue = origin.get(minIdx);
            for (int idx = 0; idx < origin.size(); idx++) {
                if (!flags[idx]) {
                    continue;
                }
                isChange = true;
                int[] curr = origin.get(idx);
                if (curr[1] == 0) {
                    if (!flags[minIdx]) {
                        minIdx = idx;
                        minValue = curr;
                    }
                    if (minValue[1] != 0) {
                        minIdx = idx;
                        minValue = curr;
                    } else if (curr[0] < minValue[0]) {
                        minIdx = idx;
                        minValue = curr;
                    }
                }
            }
            if (!isChange) {
                break;
            }

            flags[minIdx] = false;
            result.add(people[minIdx]);

            for (int idx = 0; idx < origin.size(); idx++) {
                if (!flags[idx]) {
                    continue;
                }
                int[] curr = origin.get(idx);
                if (minValue[0] >= curr[0]) {
                    curr[1]--;
                }
            }
        }

        int[][] resultArr = new int[result.size()][];
        for (int idx = 0; idx < result.size(); idx++) {
            resultArr[idx] = result.get(idx);
        }
        return resultArr;
    }
}