JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ 貪欲法 正当性証明 「区間スケジューリング問題の中でも最も原始的なものに対する貪欲法が正当であることの証明」という今更感が濃厚な内容ではあるが、最近までよく理解できていなかったということで記載する。 ＜問題設定＞ \(N\)個のタスクがあり、それぞれに対して\(1,2, \dotsc, N\)と番号が与えられている。タスク\(i\)に取り組むことにすると、時刻が半開区間\([L[i],R[i])\)に属す限りタスク\(i\)に専念し続けねばならず、他のタスクに取り掛かるのは不可能であるとする（ただし、任意のタスク\(i\)について\(L[i] \lt R[i]\)が成り立つ）。それぞれのタスクに対して「やる」「や… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2025%2F11%2F27%2F132321" title="区間スケジューリング問題に対する貪欲方針の正当性証明 - JunKobayashi&#39;s Diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2025-11-27 13:23:21 rich https://junkobayashi.hatenablog.com/entry/2025/11/27/132321 1.0 100%