In this Leetcode Queue Reconstruction by Height problem solution 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).
Problem solution in Python.
class Solution(object):
def reconstructQueue(self, people):
group = {}
for h,k in people:
if h not in group:
group[h] = []
group[h].append([h,k])
heights = sorted(group.keys(), reverse = True)
answer = []
while heights:
tallest = heights.pop(0)
if not answer:
# list of [h,k]
answer = sorted(group[tallest])
else:
# list of [h,k]
nxt_ppl = sorted(group[tallest])
tmp,i = [],0
while nxt_ppl:
h,k = nxt_ppl.pop(0)
while i < k:
tmp.append(answer.pop(0))
i += 1
tmp.append([h,k])
i += 1
answer = tmp + answer
return answer
Problem solution in Java.
class Solution {
public int[][] reconstructQueue(int[][] people)
{
int n=people.length;
int index[]=new int[n];
Arrays.sort(people,(int a[],int b[])->(a[0]-b[0]==0?b[1]-a[1]:a[0]-b[0]));
Arrays.fill(index,-1);
for(int i=0;i<n;i++)
{
int insert_ind=people[i][1];
int c=0;
for(int j=0;j<n;j++)
{
if(index[j]==-1)
insert_ind--;
if(insert_ind<0)
{
index[j]=i;
break;
}
}
}
int updated_arr[][]=new int[n][2];
for(int i=0;i<n;i++)
{
updated_arr[i][0]=people[index[i]][0];
updated_arr[i][1]=people[index[i]][1];
}
return updated_arr;
}
}
Problem solution in C++.
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
std::sort(begin(people), end(people), [](const pair<int, int> &lhs, const pair<int, int>& rhs) {
if (lhs.first > rhs.first)
return true;
if (lhs.first < rhs.first)
return false;
return lhs.second < rhs.second;
});
std::list<std::pair<int, int>> order;
for (auto person : people) {
auto it = order.begin();
std::advance(it, person.second);
order.insert(it, person);
}
return vector(begin(order), end(order));
}
Problem solution in C.
typedef struct LinkedNode {
int height;
int position;
struct LinkedNode* next;
} list;
int cmpfunc(const int* first, const int *second){
int* a = *(const int**) first;
int* b = *(const int**) second;
if(a[0] > b[0]) return 0;
else if(a[0] < b[0]) return 1;
else{
return (a[1] < b[1]? 0 : 1);
}
}
int** reconstructQueue(int** people, int peopleRowSize, int peopleColSize, int* returnSize) {
int** result = (int**)malloc(sizeof(int*)*peopleRowSize);
qsort(people, peopleRowSize, sizeof(int*), cmpfunc);
*returnSize = peopleRowSize;
list* head = (list*)malloc(sizeof(list));
head->height = 0;
head->position = 0;
head->next = NULL;
int i;
for(i = 0; i < peopleRowSize; i++){
list* tmp = head;
int j;
for(j = 0; j < people[i][1]; j++){
tmp = tmp->next;
}
list* tmp2 = (list*)malloc(sizeof(list));
tmp2->height = people[i][0];
tmp2->position = people[i][1];
tmp2->next = tmp->next;
tmp->next = tmp2;
}
for(i = 0; i < peopleRowSize; i++){
result[i] = (int*)malloc(sizeof(int)*2);
result[i][0] = head->next->height;
result[i][1] = head->next->position;
head = head->next;
}
return result;
}