Queue Reconstruction by Height
Suppose you have a queue of people, and each person has a height and a position in the queue. The position is based on the number of people in front of them who are taller. Write a function to reconstruct the queue based on the given heights and positions.
Constraints:
- The input will be a 2D array of integers, where each sub-array contains two integers: the height and the position.
- The height will be between 1 and 10^5.
- The position will be between 0 and the number of people in the queue minus one.
- The input will not be empty, and there will be at least one person in the queue.
Examples:
Input: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[7,1],[4,4]]
Explanation: The person with height 7 and position 0 is the first person in the queue, because there are no people in front of them who are taller. The person with height 4 and position 4 is the last person in the queue, because there are four people in front of them who are taller.
Solutions
Greedy Algorithm
The greedy algorithm works by sorting the people based on their heights and positions. If two people have the same height, they are sorted based on their positions. Then, we iterate through the sorted people and insert each person at their position in the result array.
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[1] < b[1] : a[0] > b[0];
}
);
vector<vector<int>> result;
for (const auto& person : people) {
result.insert(result.begin() + person[1], person);
}
return result;
}
}
;Follow-up:
What if the input is not a 2D array, but a list of objects with height and position properties?
