สมมติว่ามีบอลลูนทรงกลมจำนวนไม่มากกระจายอยู่ในพื้นที่สองมิติ สำหรับบอลลูนแต่ละลูก จะมีพิกัดเริ่มต้นและจุดสิ้นสุดของเส้นผ่านศูนย์กลางแนวนอน จุดเริ่มต้นเล็กกว่าจุดสิ้นสุดเสมอ จะมีไม่เกิน 104 ลูกโป่ง ลูกศรหนึ่งลูกสามารถยิงขึ้นในแนวตั้งได้อย่างแม่นยำจากจุดต่างๆ ตามแนวแกน x บอลลูนที่มีตำแหน่ง xstart ถึง xend ระเบิดด้วยลูกศรที่ยิงไปที่ x ถ้า xstart =x =xend ไม่จำกัดจำนวนลูกธนูที่สามารถยิงได้ สมมติให้ลูกธนูหนึ่งลูกพุ่งขึ้นไปอย่างไม่สิ้นสุด เราต้องหาจำนวนลูกศรขั้นต่ำที่ต้องยิงเพื่อระเบิดลูกโป่งทั้งหมด ดังนั้นหากอินพุตเป็นเหมือน [[10,16],[2,8], [1,6], [7,12]] ผลลัพธ์จะเป็น 2 ดังนั้นหากเรายิงจาก x =6 มันก็จะ จะระเบิด [2,8] และ [1,6] และบอลลูนอีกอันจาก x =11 เพื่อระเบิดส่วนที่เหลือ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดวิธีการที่เรียกว่า intersect() เพื่อตรวจสอบว่าตำแหน่งตัดกันหรือไม่
-
อีกวิธีหนึ่ง manipulate() เพื่อจัดการพิสัยหลังจากหาพิสัยของบอลลูนที่ตัดกันทั้งหมด
-
วิธีที่แท้จริงคือการวางตำแหน่งบอลลูนเป็น pos
-
จัดเรียงอาร์เรย์ pos ตามตำแหน่งสิ้นสุด
-
n :=จำนวนลูกโป่ง ถ้า n เป็น 0 ให้คืนค่า 0
-
currEnd :=ตำแหน่งสิ้นสุดของรายการแรกของ pos หลังจาก soring
-
cnt :=1
-
สำหรับฉันอยู่ในช่วง 1 ถึง n – 1
-
ถ้า currEnd <ตำแหน่งเริ่มต้นของ pos[i] ให้เพิ่มจำนวนขึ้น 1 และ currEnd :=ตำแหน่งสิ้นสุดของ pos[i]
-
-
จำนวนคืน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool intersect(vector <int>& a, vector <int>& b){
return a[1] >= b[0];
}
static bool cmp(vector <int>& a, vector <int>& b){
return a[1] < b[1];
}
void manipulate(vector <int>& a, vector <int>& b){
a[0] = min(a[0], b[0]);
a[1] = max(a[1], b[1]);
}
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), cmp);
int n = points.size();
if(!n) return 0;
int currEnd = points[0][1];
int cnt = 1;
for(int i = 1; i < n; i++){
if(currEnd < points[i][0]){
cnt++;
currEnd = points[i][1];
}
}
return cnt;
}
};
main(){
vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
Solution ob;
cout << (ob.findMinArrowShots(v));
} อินพุต
[[10,16],[2,8],[1,6],[7,12]]
ผลลัพธ์
2
