FilesExpand file tree

 master

/

reconstruct_queue.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

29 lines (22 loc) · 727 Bytes

 master

/

reconstruct_queue.py

Copy path

Top

File metadata and controls

• Code
• Blame

29 lines (22 loc) · 727 Bytes

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

# 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]]

def reconstruct_queue(people):

"""

:type people: List[List[int]]

:rtype: List[List[int]]

"""

queue = []

people.sort(key=lambda x: (-x[0], x[1]))

for h, k in people:

queue.insert(k, (h, k))

return queue