【アルゴリズム脳トレ】leetcode medium 435 non-overlapping intervals

こんにちは

今回の学びは

・interval問題は並べて考えろ

・greedyが使えるかどうかの判断は〇〇かどうか。

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

ちょっとわかりにくいですね。

重複mtgはとにかく省いて。で省くmtgは最初にして。

という問題。

パッと見、難しいです。

15分以上考えましたが、

なんとなく被ったら、弾くを繰り返せばいいんじゃないか。

コーディング初めて複雑すぎて断念。見当違いな気もするし、時間もたったし

解答を見ることに。

そこにあった解答はgreedy

なんとなくいけそうな気もするけど、それは深い思考木のような気がして怖くて

考えなかった。俗にいうスルー

https://leetcode.com/problems/non-overlapping-intervals/discuss/371541/Python-Greedy-Solution

では

どいういう時にgreedyが使えると、判断できるのだろうか？

いつ使えるか？
という疑問、まずはぐぐる前に自分で考えよう
think yourself before google
TYBG
考えてからググれ　（を常に心がけましょう）
つまりは仮説をたてよ。建てれる水平思考できる、頭を鍛えておきましょう
というと。

で
私の考えは、
・他に良さそうなアルゴリズムが思いつかなかった時。
・サンプルケースがgreedyで通った時

の二つかな。
ではググろう。

https://www.quora.com/When-does-the-greedy-algorithm-fail
ここで特筆すべきは
たくさん問題解いとけ。とけなくても2、３時間考えろ、それを繰り返せ、とう精神論っぽいが正攻法なアドバイス。
と
matroidっていうのを知っておこう
https://ja.wikipedia.org/wiki/マトロイド

あと
inputが段階ごとに増えて、その順番が解答に関与しないとき
greedyは使える、と書いている。わけがわからん。

そもそも
貪欲法(greedy algorithm)とは？
問題を小さく切って、その都度局所解を求める。場合によっては次にそれをつなげる
を繰り返すアルゴリズム。
なんと、ダイクストラも貪欲法なんだって。結構使えるんじゃん

もちろん
ナップサックとか解けない問題もある。

この貪欲法。
問題小さく切って、次に持ち越す、ってどっかで来たこたがあるような
そう
動的計画法の未熟版みたいなものって考えてもいいかも

貪欲法で溶ける問題は、dpにしても必ず解けるのだ。
ただし、その逆は必ずしもできるとは限らない

ということで、貪欲法が使える問題とは

・問題が小分けにできそうで

・かつ局所解だけ引き継げばよく、局所解は上書きされることなく(dpみたいに複雑な関係性はない）

・入力が段階的に上がっていっていて、つまりはソートができそうな時

これらの条件を満たせば満たすほど

貪欲解で最適解が求まる可能性が高くなるぞ。

長いで一行にキャッチーに整理すると、「ソートできて局所解が出せそなのは貪欲法でも。」と記しておく

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　

貪欲かいの場合ですとO(n)です

実際の実装はこちら

こういう答えを見たときもできれば自分で書くよにしましょう。写経でも構わないので。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if intervals is None or len(intervals) == 0: return 0
        #intervals = sorted(intervals, key = lambda x: x[0])
        intervals.sort(key = lambda x: x[0])
        end = intervals[0][1]
        overlapped = 0
        for i in range(1, len(intervals)):
            s, e = intervals[i]
            if s < end:
                overlapped += 1
                #以下の条件で2と3は通ります！1はダメです
                #1#end = max(e, end)
                #2#works
                end = min(e, end)
                #3#worked
                # if e < end:
                #     end = e
            else:
                end = e
        return overlapped

実装後です。timespace analysis (時間とスペースの分析）は　◯◯

O(n)でした

まとめ

・ソートできて局所解が出せそなのは貪欲法でも。

・think yourself before google

以上です