19주차(Minimum Number of Arrows to Burst Balloons)

디렉토리:

이번 주 문제 완성

주요 과정 사고방식

1. 이번 주에 문제 완성

이번 주에는 총 1문항, 1문항을 완성했다.
구체적인 완성 문제 및 난이도는 다음과 같다.
#
Title
Difficulty
452
Minimum Number of Arrows to Burst Balloons
Medium

제목 내용

1、Minimum Number of Arrows to Burst Balloons　 There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

제목 대의: 본 문제에는 풍선의 범위가 있는데, 발사된 아로우가 이 범위에서 이 풍선이 터진다.모든 풍선의 범위에서 최소한 모든 풍선을 뚫을 수 있는arrow 수를 구하세요.

2. 주요 과정 사고방식

1、Minimum Number of Arrows to Burst Balloons：

우선 범위 서열에 대해 한 차례 정렬을 진행한다.정렬의 규칙은 최대치가 같은지 아닌지를 우선적으로 판단하는 것이다.같으면 최소값으로 정렬하고, 반대로 최대값으로 오름차순으로 정렬한다.정렬을 한 후에 매번 다음 수의 최소값과 ARrow의 값을 비교합니다. 최소값이 ARrow보다 크면 ARrow가 이 범위에 있지 않다는 것을 의미합니다. (현재 범위의 최대값을 ARrow로 하여 가장 많은 범위를 뚫을 수 있도록 합니다.) count++.그룹의 끝까지 접근하면count의 값을 얻을 수 있습니다.

3. 관련 코드

Minimum Number of Arrows to Burst Balloons

class Solution {
public:
     int findMinArrowShots(vectorint, int>>& points) {
        int count = 0, arrow = INT_MIN;
        sort(points.begin(), points.end(), mysort);
        for(int i = 0; iif(arrow!=INT_MIN && points[i].first<=arrow){continue;} //former arrow shot points[i] 
            arrow = points[i].second; // new arrow shot the end of points[i]
            count++;
        }
        return count;
      }
      static bool mysort(pair<int, int>& a, pair<int, int>& b){
        return a.second==b.second?a.first

19주차(Minimum Number of Arrows to Burst Balloons)