forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathreconstruct_queue.py
More file actions
27 lines (22 loc) · 725 Bytes
/
reconstruct_queue.py
File metadata and controls
27 lines (22 loc) · 725 Bytes
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