algorithms/algorithms/queue/reconstruct_queue.py at main · keon/algorithms

35 lines (26 loc) · 940 Bytes

"""

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

Provide feedback