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 <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
8 sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
9 return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
10 });
11
12 vector<vector<int>> queue;
13 for (auto& person : people) {
14 queue.insert(queue.begin() + person[1], person);
15 }
16
17 return queue;
18}
19
20int main() {
21 vector<vector<int>> people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
22 vector<vector<int>> result = reconstructQueue(people);
23
24 for (auto& person : result) {
25 cout << "[" << person[0] << ", " << person[1] << "] ";
26 }
27
28 return 0;
29}This C++ solution sorts the people first by height in descending order and then by the number in ascending order. The solution utilizes the C++ STL sort with a custom lambda function as a comparator. After sorting, the approach iterates over the sorted array, inserting each person at the correct index dictated by their second value.