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