Re: [閒聊] 每日LeetCode

[fxfxxxfxx (愛麗絲)]

452. Minimum Number of Arrows to Burst Balloons

今天的題目蠻有水準的，我覺得很值得寫
方法很容易想，要證明卻不是很容易

給你一堆區間，[x_{start}, x_{end}], ...
要你找出一組 a_1, ..., a_n 使得每個區間都包含至少一個點
問所需最少的點的數量

直覺上就是要找出最長的不重疊區間序列
剩下的是證明這是最佳解

首先，很明顯最佳解一定 >= 這個序列的長度
因為兩兩都不重疊，一個點最多對應到一個區間
答案不可能比這還要好

剩下的是去證最佳解 <= 這個序列的長度
也就是真的能建構出一組和這個序列一樣長的解

老實說我想了一陣子也不知道怎麼證
後來發現從我實作最長不重疊區間的演算法來證的話變得很容易

  先對右端點做排序，接著對每一個新的區間
  如果加入後不會重疊就加入，否則捨棄

我發現如果不斷將點設在加入的區間的最右端
因為被捨棄掉代表他包含了某個我們加入的區間的右端點
自然而然最後的結果是一組合法的解
再根據之前說的，答案不可能比最長不重疊序列好
所以最佳解不多不少就是最長不重疊序列

至於這個演算法的結果為什麼是最長不重疊區間
我們可以證明，考慮完一個新的區間之後的結果都是有最小右端點的最佳解
對於一個新的區間，有兩種可能，加入或不加入
如果跟原本的解不重疊當然加入一定是當下唯一的最佳解
如果重疊的話，因為目前的答案是有最小右端點的最佳解
因此所有最佳解都一定和新的點重疊，加入一定不會比較好，可以直接捨棄

    class Solution {
    public:
        int findMinArrowShots(vector<vector<int>>& points) {
            using T = pair<int, int>;
            sort(points.begin(), points.end(), [](const auto& x, const auto& y){
                return T{x[1], x[0]} < T{y[1], y[0]};
            });

            int ans = 0;
            int64_t prev = numeric_limits<int64_t>::min();
            for (auto& p: points) {
                int st = p[0], ed = p[1];
                if (st <= prev) continue;
                prev = ed;
                ans += 1;
            }
            return ans;
        }
    };

這題還蠻不錯的

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672887521.A.6B6.html
→ Jaka: 大師
推 PyTorch: 大師
→ Rushia: 這題我覺得不是很好想
推 NTHUlagka: 問個跟題目無關的 為什麼要用int64_t啊 那個的好處是
→ NTHUlagka: 什麼
→ NTHUlagka: 這題我的想法會是用樹狀結構去找這樣的交集 而不是用
→ NTHUlagka: 排序 感覺排序的好像更簡潔點
→ fxfxxxfxx: 因為最小會到-2^{31} 要保證不重疊的話要更小
→ fxfxxxfxx: 我指prev的初始值
推 NTHUlagka: 那個我想問的是long long跟int64_t 的選擇上有什麼差
→ NTHUlagka: 異呢
→ fxfxxxfxx: 字母比較少XD 而且在任何環境大小都不會變 比較明確
推 NTHUlagka: 哈哈好 了解 想說在leetcode上兩個應該都行
→ NTHUlagka: 感謝