Sponsored
Sponsored
In this approach, we first sort the array of people. The sorting criteria should be descending order of height and ascending order of the number of people in front for the same height. After sorting, we iterate through the list and insert each person into a new list at the index corresponding to the number of people in front of them. This ensures that each person is placed correctly with regard to the number of taller or equally tall people in front.
Time Complexity: O(n^2) due to the potential element shifting during insertion.
Space Complexity: O(1) additional space required.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Comparator function for sorting
5int compare(const void* a, const void* b) {
6 int* personA = *(int**)a;
7 int* personB = *(int**)b;
8
9 if (personA[0] != personB[0])
10 return personB[0] - personA[0];
11 return personA[1] - personB[1];
12}
13
14void queueReconstruction(int** people, int peopleSize, int* peopleColSize, int** returnColumnSizes) {
15 qsort(people, peopleSize, sizeof(int*), compare);
16 int** queue = malloc(sizeof(int*) * peopleSize);
17 int queueSize = 0;
18
19 for (int i = 0; i < peopleSize; i++) {
20 int k = people[i][1];
21 // Shift elements if necessary
22 for (int j = queueSize; j > k; j--) {
23 queue[j] = queue[j - 1];
24 }
25
26 queue[k] = people[i];
27 queueSize++;
28 }
29
30 *returnColumnSizes = (int*)malloc(sizeof(int) * peopleSize);
31 for (int i = 0; i < peopleSize; i++) {
32 (*returnColumnSizes)[i] = 2;
33 }
34
35 // Display result (example for demonstration)
36 printf("[");
37 for (int i = 0; i < peopleSize; i++) {
38 printf("[%d, %d]", queue[i][0], queue[i][1]);
39 if (i < peopleSize - 1) printf(", ");
40 }
41 printf("]");
42
43 free(queue);
44}
45
46int main() {
47 int arr[][2] = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
48 int* people[] = {arr[0], arr[1], arr[2], arr[3], arr[4], arr[5]};
49 int peopleColSize[] = {2, 2, 2, 2, 2, 2};
50 int* returnColumnSizes;
51
52 queueReconstruction(people, 6, peopleColSize, &returnColumnSizes);
53
54 return 0;
55}This C solution sorts the list with a custom comparator and then builds the resulting queue by inserting each person at their k-th index. The qsort is used for sorting the list based on the height in descending order and the k-value in ascending order. We use an auxiliary array to store the reconstructed queue, shifting elements as needed during insertion to maintain order.