406. Queue Reconstruction by Height

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.

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]]

 

Example

Solution:

<?php

class Solution {

    /**
     * @param Integer[][] $people
     * @return Integer[][]
     */
    function reconstructQueue($people) {
        usort($people, function($p1, $p2){
            return ($p1[0] !== $p2[0])?
                 $p2[0] <=> $p1[0] : $p1[1] <=> $p2[1];
        });
        $result = [];
        foreach($people as $p){
            array_splice($result, $p[1], 0, [$p]);
        }

        return $result;
    }
}

?>

 

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

The higher the person is, the more importance it has for other persons

  • So starting sort by height, DESC
  • Then for each height level, sort by # of higher heads in the front, ASC
  • (Just like ‘ORDER BY h DESC, k ASC’ in SQL)

Now we have:

More Important to Others <===> Less Important to Others

[7,0]    [7,1]     [6,1]    [5,0]    [5,2]   [4,4]

Then set group height = 7 to the result

[7,0] [7,1]  ;   TBD: [6,1]    [5,0]    [5,2]   [4,4]

Now set group  height = 6. It could be places any where, since h=7 can’t see them, so the position is determined by their value of k. for example: [6,1]. there’s one higher/equal height person ahead, we can simply insert it right after k is matched, and push everyone else backwards safely since they don’t care about lower person moving around.

   0     1     2     3     4  ..... (index)

[7,0] [6, 1] [7,1]  ;                TBD:    [5,0]    [5,2]   [4,4]

[5,0] [7,0] [6, 1] [7,1]  ;          TBD:    [5,2]   [4,4]

[5,0] [7,0] [5,2] [6, 1] [7,1]  ;    TBD:    [4,4]

[5,0] [7,0] [5,2] [6, 1] [4,4]  [7,1]

 

 

In PHP, array_splice($result, $p[1], 0, [$p]);  means insert p to position p[i] and move people behind backwards

In Java, LinkedList seems easier.

In Python, there’s even easier method (list.insert(index, value))

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.