-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathreconstruct_queue.py
More file actions
35 lines (26 loc) · 940 Bytes
/
reconstruct_queue.py
File metadata and controls
35 lines (26 loc) · 940 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
28
29
30
31
32
33
34
35
"""
Reconstruct Queue by Height
Given a list of people described by (height, k) pairs where k is the
number of taller-or-equal people in front, reconstruct the queue by
sorting and inserting.
Reference: https://leetcode.com/problems/queue-reconstruction-by-height/
Complexity:
Time: O(n^2)
Space: O(n)
"""
from __future__ import annotations
def reconstruct_queue(people: list[list[int]]) -> list[list[int]]:
"""Reconstruct the queue from (height, k) pairs.
Args:
people: List of [height, k] pairs.
Returns:
The reconstructed queue as a list of [height, k] pairs.
Examples:
>>> reconstruct_queue([[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]])
[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
"""
queue: list[list[int]] = []
people.sort(key=lambda x: (-x[0], x[1]))
for height, count in people:
queue.insert(count, [height, count])
return queue