Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

題目：
給你一串氣球陣列
用垂直x軸的箭射破他們
擦到邊就可以了
問你最少要幾隻箭矢
直接舉例說明比較快= =
[[1,3][3,7][10,11][10,12]]
這裡的氣球需要兩隻箭
射過3跟11
就可以射破全部氣球了

解法：
反正都要看氣球
就先排序好了

排序之後
一次射一隻箭矢
一隻箭矢能破壞掉所有重疊的氣球當然最好
所以就一直往右邊找
直到沒辦法再一次射破更多
就換下一隻箭矢
然後
對ㄚ= =





```cpp
class Solution {
public:

    static bool compare(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }

    int findMinArrowShots(vector<vector<int>>& points)
    {

        sort(points.begin(), points.end(), compare);

        int len = points.size();

        int res = 0;

        int lp = 0;
        int rp = 0;

        for(int i = 0 ; i < len ;)
        {

            res ++;

            lp = points[i][0];
            rp = points[i][1];

            i++;

            while(i<len)
            {

                if(points[i][0] > rp)
                {
                    break;
                }
                else if(points[i][0] == rp)
                {
                    while(i < len && points[i][0] == rp)
                    {
                        i ++;
                    }
                    break;
                }
                else if(points[i][0] > lp)
                {
                    lp = points[i][0];
                }

                if(points[i][1] < rp)
                {
                    rp = points[i][1];
                }

                if(lp == rp)
                {
                    while(i < len && points[i][0] == rp)
                    {
                        i ++;
                    }
                    break;
                }

                i++;

            }
        }

        // for(auto k : points)
        // {
        //     cout << "[" << k[0] << "," << k[1] << "]" ;
        // }

        return res;

    }
};
```









--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.57.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1710732944.A.FB7.html
→ digua: 大師
→ oin1104: 好了啦 中正資工書卷獎 要這樣謙虛喔 我吐了
推 digua: ☺ ?
→ digua: 我被當欸
→ digua: 恨你
→ oin1104: 誰不知道你被當體育室因為你是體力很差的病弱小男娘 又
→ oin1104: 在那邊靠腰 我哭了
→ Rushia: 檢查右邊就好了ㄅ
→ oin1104: 確實 只要有rp就可以射破氣球了 其實lp好像不用
→ oin1104: 愛rp
推 pysunsun: 地瓜是中字輩卷哥喔？我要含你的雞巴了
→ oin1104: 甲甲退散
推 digua: 到底在供三小
→ amsmsk: 他媽的又在溝假
推 sustainer123: 你版剩我讀學店了