-
Notifications
You must be signed in to change notification settings - Fork 35
/
_406.java
executable file
·52 lines (46 loc) · 1.51 KB
/
_406.java
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
package com.hit.basmath.interview.top_interview_questions.hard_collection.others;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
/**
* 406. Queue Reconstruction by Height
* <p>
* Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
* <p>
* Note:
* <p>
* The number of people is less than 1,100.
* <p>
* Example
* <p>
* Input:
* <p>
* [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
* <p>
* Output:
* <p>
* [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
*/
public class _406 {
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0)
return new int[0][0];
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (b[0] == a[0]) return a[1] - b[1];
return b[0] - a[0];
}
});
int n = people.length;
ArrayList<int[]> tmp = new ArrayList<>();
for (int i = 0; i < n; i++)
tmp.add(people[i][1], new int[]{people[i][0], people[i][1]});
int[][] res = new int[people.length][2];
int i = 0;
for (int[] k : tmp) {
res[i][0] = k[0];
res[i++][1] = k[1];
}
return res;
}
}