Difficulty: Medium

Suppose you have an out-of-order group of people standing in a queue, and the array people represents the attributes of some people in the queue (not necessarily in order). Each people[I] = [hi, ki] means that the ith person is hi, and there are exactly ki people in front of them who are hi or higher.

You reconstruct and return the queue represented by the input array people. The returned queue should be formatted as an array queue, where Queue [j] = [hj, kj] is the property of the JTH person in the queue (queue[0] is the person at the front of the queue).

Their thinking

There are two ways:

• Method 1: high priority row, high front can be randomly inserted into the low, does not affect its attributes, so can be arbitrarily inserted forward, high is moved back;
• Method two: low priority row, so high row casually, see empty insert can. It just doesn’t matter.

Answer key

public int[][] reconstructQueueTallerFirst(int[][] people) {
    Arrays.sort(people, (o1, o2) -> o1[0] == o2[0]? o1[1] - o2[1] : o2[0] - o1[0]);
    List<int[]> reconstructionList = new ArrayList<>(people.length);
    for (int[] p : people) {
        reconstructionList.add(p[1], p);
    }
    return reconstructionList.toArray(new int[people.length][]);
}

public int[][] reconstructQueueShorterFirst(int[][] people) {
    Arrays.sort(people, (o1, o2) -> o1[0] == o2[0]? o2[1] - o1[1] : o1[0] - o2[0]);
    int length = people.length;
    int[][] reQueue = new int[length][];
    for (int[] p : people) {
        int spaces = p[1] + 1;
        for (int i = 0; i < length; i++) {
            if(reQueue[i] ! =null) continue;
            --spaces;
            if(spaces ! =0) continue;
            reQueue[i] = p;
            break; }}return reQueue;
}
Copy the code

test

QueueReconstructionByHeight queueReconstructionByHeight = new QueueReconstructionByHeight();

@Test
public void taller_first_test_case1(a) {
    int[][] people = new int[] [] {{7.0},
            {4.4},
            {7.1},
            {5.0},
            {6.1},
            {5.2}};int[][] expected = new int[] [] {{5.0},
            {7.0},
            {5.2},
            {6.1},
            {4.4},
            {7.1}}; Assertions.assertArrayEquals(expected, queueReconstructionByHeight.reconstructQueueTallerFirst(people)); }@Test
public void taller_first_test_case2(a) {
    int[][] people = new int[] [] {{6.0},
            {5.0},
            {4.0},
            {3.2},
            {2.2},
            {1.4}};int[][] expected = new int[] [] {{4.0},
            {5.0},
            {2.2},
            {3.2},
            {1.4},
            {6.0}}; Assertions.assertArrayEquals(expected, queueReconstructionByHeight.reconstructQueueTallerFirst(people)); }@Test
public void shorter_first_test_case1(a) {
    int[][] people = new int[] [] {{7.0},
            {4.4},
            {7.1},
            {5.0},
            {6.1},
            {5.2}};int[][] expected = new int[] [] {{5.0},
            {7.0},
            {5.2},
            {6.1},
            {4.4},
            {7.1}}; Assertions.assertArrayEquals(expected, queueReconstructionByHeight.reconstructQueueShorterFirst(people)); }@Test
public void shorter_first_test_case2(a) {
    int[][] people = new int[] [] {{6.0},
            {5.0},
            {4.0},
            {3.2},
            {2.2},
            {1.4}};int[][] expected = new int[] [] {{4.0},
            {5.0},
            {2.2},
            {3.2},
            {1.4},
            {6.0}}; Assertions.assertArrayEquals(expected, queueReconstructionByHeight.reconstructQueueShorterFirst(people)); }Copy the code