สมมติว่าเรามีซองจดหมายบางซอง ซองจดหมายเหล่านี้มีค่าความสูงและความกว้างเป็นคู่ เราสามารถใส่ซองหนึ่งเข้าไปในอีกซองหนึ่งได้หากความสูงและความกว้างของซองที่สองทั้งสองมีขนาดเล็กกว่าความสูงและความกว้างของซองแรก แล้วจำนวนซองสูงสุดที่เราใส่เข้าไปได้จะเป็นเท่าไหร่ ดังนั้น หากอินพุตเป็น [[5,5], [6,4], [6,8], [2,3]] เอาต์พุตจะเป็น 3 เนื่องจากซองที่เล็กที่สุดคือ [2,3] จากนั้น [5,5] แล้วก็ [6,8].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- จัดเรียงอาร์เรย์ v ตามความสูง เมื่อความสูงเท่ากัน เปรียบเทียบกับความกว้าง
- ถ้าขนาดของ v เท่ากับ 0 แล้ว −
- คืน 0
- กำหนดอาร์เรย์ ret
- สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- กำหนดอาร์เรย์ชั่วคราว =v[i]
- x :=อุณหภูมิ[1]
- ต่ำ :=0, สูง :=ขนาดของ ret, curr :=0
- ในขณะที่ต่ำ <=สูง ทำ −
- กลาง :=ต่ำ + (สูง - ต่ำ) / 2
- ถ้า ret[กลาง]
- curr :=กลาง + 1
- ต่ำ :=กลาง + 1
- มิฉะนั้น
- สูง :=กลาง - 1
- ถ้า curr <0 แล้ว −
- ไม่ต้องสนใจตอนต่อไป ข้ามไปที่ตอนต่อไป
- ถ้า curr>=ขนาดของ ret แล้ว −
- ใส่ temp[1] ที่ส่วนท้ายของ ret
- มิฉะนั้น
- ret[curr] :=temp[1]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector <int> a, vector <int> b){
if(a[0] == b[0])return a[1] > b[1];
return a[0] < b[0];
}
int maxEnvelopes(vector<vector<int>>& v) {
sort(v.begin(), v.end(), cmp);
if(v.size() == 0)return 0;
vector <int> ret;
for(int i = 0; i < v.size(); i++){
vector <int> temp = v[i];
int x = temp[1];
int low = 0;
int high = ret.size() -1;
int curr = 0;
while(low <= high){
int mid = low + (high - low) / 2;
if(ret[mid]<temp[1]){
curr = mid + 1;
low = mid + 1;
}else{
high = mid - 1;
}
}
if(curr < 0) continue;
if(curr >= (int)ret.size()){
ret.push_back(temp[1]);;
}else{
ret[curr] = temp[1];
}
}
return ret.size();
}
};
main(){
Solution ob;
vector<vector<int>> v = {{5,5}, {6,4}, {6,8}, {2,3}};
cout << (ob.maxEnvelopes(v));
} อินพุต
{{5,5}, {6,4}, {6,8}, {2,3}} ผลลัพธ์
3
