2022.01.02 - SX09-14.根据身高重建队列

2022.01.02 - SX09-14.根据身高重建队列

文章目录

• 1. 题目
• 2. 思路
• • (1) 贪心算法
• 3. 代码

1. 题目

2. 思路 (1) 贪心算法

• 贪心策略是优先安排小个子，根据小个子属性中的k值，为其前面留够k个空位即可，因为后面被安排的人必然比其要高。
• 需要对原来的数组进行排序，小个子在前，高个子在后，若两个人的身高相等，则按照k值从大到小进行排序，因为k值中包含了相等身高的人。

3. 代码

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

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
            }
        });
        int n = people.length;
        int[][] res = new int[n][];
        for (int[] person : people) {
            int space = person[1];
            for (int i = 0; i < n; i++) {
                if (res[i] == null) {
                    if (space > 0) {
                        space--;
                    } else {
                        res[i] = person;
                        break;
                    }
                }
            }
        }
        return res;
    }
}