BOJ #11000

LEVEL :
Gold5
質問の概要:
最小限の教室ですべての授業を受けなければならない.
ソリューション:
肝心なのは時間の複雑さを最小限に抑えて問題を解決することだ.
問題を見ると,まず考えられる方法は,現在のカリキュラムリストの開始時間が速い順に並べ替え,貪欲にアルゴリズムを実行させる際に漏れがないようにすることである.そして整理されたカリキュラムリストを一つ一つ弾き出し、whileドアを迂回して弾けるカリキュラムリストがなくなるまで教室にgeedyと並べます.
現在のカリキュラムリストの開始時間が既存の教室の終了時間以上である場合、既存の教室の完了値を変更し、上記の条件を満たす教室がない場合はnew教室を形成する形で行います.
このとき,カリキュラムディレクトリをすべて回転させるためにwhileはN回の演算を尋ね,そのカリキュラムのディレクトリがどの教室に属するかを決定する際,最悪の場合,授業ごとに新しい教室が必要になる可能性があるため,カリキュラムディレクトリの個数をN回比較する必要があるため,時間複雑度はO(n^2)である.
結果はもちろん...タイムアウト.

Solution1. -> FAIL

import sys

if __name__ == "__main__" :
    n = int(input().strip())
    arr = [list(map(int,input().strip().split()))for _ in range(n)]
    arr.sort()
    classroom = []
    while(arr) :
        start,finish = arr.pop(0)
        if not classroom :
            classroom.append([start,finish])
            continue
            
        for i in range(len(classroom)) :
            if classroom[i][1] <= start :
                classroom[i][1] = finish
                break
            else:
                if i == len(classroom)-1 :
                    classroom.append([start,finish])
                    break
                    
    print(len(classroom))

それはどうですか.まず、各課の目次を比較する教室に入れるためにGETのプロセスN回演算は減らないので、その課程の目次がどの教室に属するかを確認するために、比較プロセスの時間的複雑さを減らそうとする.このためheapq,すなわち優先キューの概念を用いた.
heapify schoolは、完了時間が速い優先キューを形成します.すなわち、完了時間の最小値は常に0の位置にあります.
もちろん,pushプロセスとpop後の教室heapifyプロセスはlognの時間的複雑さを有する.
結論として,教室を挿入する際は常に優先順位を保ち,過程を比較する必要はなく,push過程とpop後の教室heapify過程の時間的複雑さを考慮すればよい.

Solution2. -> SUCCESS

import sys
import heapq

if __name__ == "__main__" :
    n = int(input().strip())
    arr = [list(map(int,input().strip().split()))for _ in range(n)]
    arr = sorted(arr, key=lambda x:x[0])
    
    classroom = []
    heapq.heapify(classroom)
    heapq.heappush(classroom, arr[0][1])
                    
    for i in range(1,n) :
        start = arr[i][0]
        finish = arr[i][1]
        if classroom[0] <= start :
                heapq.heappop(classroom)
                heapq.heappush(classroom,finish)
        else : 
            heapq.heappush(classroom,finish)
    
    print(len(classroom))

時間の複雑さ:

パーソナルカリキュラムリストgetの複文for:N回演算

heapqのheapify、pushの演算に用いる:logn次演算

= NlogN
O(NlogN)
考察:

優先キューの概念を再定義する必要があるようです...:heapq参考資料

greedyアルゴリズムは最適解を解くための近似法であり,多くの場合,そのうちの1つの問題を決定する必要があるたびに,その瞬間に最適な問題を選択して解き,最終的に最適解に達する.一瞬一瞬の選択は地域的にその瞬間にとって最良であるが、これらの選択を集め続け、最終的な(グローバルな)答えを出すと、それが最良であることは保証されない.しかしgreedyアルゴリズムを適用できる問題は地域的でグローバルな最適な問題である.貪欲アルゴリズムが良好に動作する問題の多くは,貪欲選択条件(greedy choice property)と最適局所構造条件(optimalサブ構造)の2つの条件を満たす.貪欲な選択条件は,前の選択が後の選択に影響を及ぼさず,最適な局所構造条件が問題に対する最適解が局所問題に対しても最適である.これらの条件が成立しなければ,貪欲アルゴリズムは最適解を求めることができない.

参考資料:

https://ko.wikipedia.org/wiki/貪欲なアルゴリズム

https://chanhuiseok.github.io/posts/ds-4/