Question

406. Queue Reconstruction by Height

中文文档

Description

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] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

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] = [hj, kj] is the attributes of the jth 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 <= hi <= 106
• 0 <= ki < people.length
• It is guaranteed that the queue can be reconstructed.

Solutions

Solution 1

class Solution:
  def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
    people.sort(key=lambda x: (-x[0], x[1]))
    ans = []
    for p in people:
      ans.insert(p[1], p)
    return ans

class Solution {
  public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
    List<int[]> ans = new ArrayList<>(people.length);
    for (int[] p : people) {
      ans.add(p[1], p);
    }
    return ans.toArray(new int[ans.size()][]);
  }
}

class Solution {
public:
  vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
      return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
    });
    vector<vector<int>> ans;
    for (const vector<int>& p : people)
      ans.insert(ans.begin() + p[1], p);
    return ans;
  }
};

func reconstructQueue(people [][]int) [][]int {
  sort.Slice(people, func(i, j int) bool {
    a, b := people[i], people[j]
    return a[0] > b[0] || a[0] == b[0] && a[1] < b[1]
  })
  var ans [][]int
  for _, p := range people {
    i := p[1]
    ans = append(ans[:i], append([][]int{p}, ans[i:]...)...)
  }
  return ans
}