FilesExpand file tree

 master

/

QueueReconstructionByHeight406.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (41 loc) · 1.17 KB

 master

/

QueueReconstructionByHeight406.java

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (41 loc) · 1.17 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* 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.

*

* Note:

* The number of people is less than 1,100.

*

*

* Example

*

* Input:

* [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

*

* Output:

* [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

*

*/

public class QueueReconstructionByHeight406 {

public int[][] reconstructQueue(int[][] people) {

int y = people.length;

if (y == 0) return people;

Arrays.sort(people, new SortRule());

LinkedList<int[]> res = new LinkedList<>();

for(int[] p: people){

res.add(p[1], p);

}

return res.toArray(new int[people.length][]);

}

class SortRule implements Comparator<int[]> {

@Override

public int compare(int[] a, int[] b) {

int diff = a[0] - b[0];

if (diff < 0) return 1;

else if (diff > 0) return -1;

else return a[1] - b[1];

}

}

}