Queue Reconstruction by Height

Greedy

# Solution

# Greedy Algorithm

Algorithm:

• sort people:
• in the descending order by height
• among the guys of the same height, in the ascending order by k-values
• take guys one by one, and place them in the output array at the indexes equal to their k-values.
• return output array

Basically there are 2 steps. First, we handle the people from tallest (largest `h`) to shortest b/c the short people don't affect `k` of tall ones. People w/ lower `k` are before the higher in `res`ult. Then, we keep inserting to `k`th position the next tallest person.

``````def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
res = []
people.sort(key = lambda elt: (-elt[0], elt[1]))
for person in people:
res.insert(person[1], person)
return res
``````
1
2
3
4
5
6

a solution by CX, still haven't understood

``````def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
n = len(people)

res = [(n, -1) for _ in range(n)]
people.sort(key = lambda elt: (elt[0], -elt[1]))

idx = 0
for i in range(n):
if res[i][1] != -1: # already filled, continue
continue
j = idx
while j < n:
if people[j][1] == 0: # find i-th person
break
j += 1
res[i] = people[j]
for k in range(idx, j):
# find pos of ppl w/ height <= i-th person
pos = i
cnt = 0
total = people[k][1] - 1
while cnt < total or res[pos][1] != -1:
if res[pos][1] == -1:
cnt += 1
pos += 1
res[pos] = people[k]
idx = j + 1

return res
``````
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