Description (leetcode)

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [h_i, k_i] represents the i^th person of height h_i with exactly k_i other people in front who have a height greater than or equal to h_i.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [h_j, k_j] is the attributes of the j^th person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[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]]

Explanation:

Person 0 has height 5 with no other people taller or the same height in front.

Person 1 has height 7 with no other people taller or the same height in front.

Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.

Person 3 has height 6 with one person taller or the same height in front, which is person 1.

Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.

Person 5 has height 7 with one person taller or the same height in front, which is person 1.

Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]

Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

  • 1 <= people.length <= 2000
  • 0 <= h_i <= 10^6
  • 0 <= k_i < people.length
  • It is guaranteed that the queue can be reconstructed.

submission

impl Solution {
    // The problem hint we should iterate person from shortest to highest
    // the way this works is we place each person at the kth empty place
    // the tricky part here is how we search for the kth empty place.
    // An easier solution would be iterate them from highest to shortest,
    // since we place the higher person first, we know exactly where to
    // put them at each step, the caveat here is each insertion is O(n)
    // which makes our solution overall O(n^2)
    pub fn reconstruct_queue(mut people: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        people.sort_by_key(|p| (-p[0], p[1]));
        let mut ans = Vec::with_capacity(people.len());
        for person in people {
            let idx = person[1] as usize;
            ans.insert(idx, person);
        }
        ans
    }
}