0406 solved.

liuyubobobo · liuyubobobo · commit dce82fb8dd9b · 2022-06-29T12:14:48.000-07:00
diff --git a/0001-0500/0406-Queue-Reconstruction-by-Height/cpp-0406/CMakeLists.txt b/0001-0500/0406-Queue-Reconstruction-by-Height/cpp-0406/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_0406)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0406 main.cpp)
diff --git a/0001-0500/0406-Queue-Reconstruction-by-Height/cpp-0406/main.cpp b/0001-0500/0406-Queue-Reconstruction-by-Height/cpp-0406/main.cpp
@@ -0,0 +1,53 @@
+/// Source : https://leetcode.com/problems/queue-reconstruction-by-height/
+/// Author : liuyubobobo
+/// Time   : 2022-06-29
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
+
+/// Greedy
+/// Time Complexity: O(nlogn + n^2)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
+
+        sort(people.begin(), people.end(),
+             [](const vector<int>& p1, const vector<int>& p2){
+            if(p1[0] != p2[0]) return p1[0] > p2[0];
+            return p1[1] < p2[1];
+        });
+
+        vector<vector<int>> res = {people[0]};
+        for(int i = 1; i < people.size(); i ++){
+
+            int j = 0, cnt = 0;
+            for(; j < (int)res.size() && cnt < people[i][1]; j ++){
+                if(res[j][0] >= people[i][0]) cnt ++;
+            }
+
+            auto iter = res.begin() + j;
+            res.insert(iter, people[i]);
+        }
+        return res;
+    }
+};
+
+
+void print_vec(const vector<vector<int>>& v){
+    for(const vector<int>& p: v)
+        cout << '(' << p[0] << ',' << p[1] << ')';
+    cout << '\n';
+}
+
+int main() {
+
+    vector<vector<int>> people1 = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
+    print_vec(Solution().reconstructQueue(people1));
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -439,7 +439,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 403 | [Frog Jump](https://leetcode.com/problems/Frog-Jump/) | [solution](https://leetcode.com/problems/Frog-Jump/)<br/>[缺：dp] | [C++](0001-0500/0403-Frog-Jump/cpp-0403/) | | |
 | 404 | [Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/) | [无] | [C++](0001-0500/0404-Sum-of-Left-Leaves/cpp-0404/) | | |
 | 405 | [Convert a Number to Hexadecimal](https://leetcode.com/problems/convert-a-number-to-hexadecimal/) | [无] | [C++](0001-0500/0405-Convert-a-Number-to-Hexadecimal/cpp-0405/) | | |
-| | | | | | |
+| 406 | [Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/) | [无] | [C++](0001-0500/0406-Queue-Reconstruction-by-Height/cpp-0406/) | | |
 | 407 | [Trapping Rain Water II](https://leetcode.com/problems/trapping-rain-water-ii/) | [无] | [C++](0001-0500/0407-Trapping-Rain-Water-II/cpp-0407/) | | |
 | | | | | | |
 | 410 | [Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/) | [solution](https://leetcode.com/problems/split-array-largest-sum/solution/) [题解](https://leetcode-cn.com/problems/split-array-largest-sum/solution/fen-ge-shu-zu-de-zui-da-zhi-by-leetcode/) | [C++](0001-0500/410-Split-Array-Largest-Sum/cpp-410/) | | |
