以下把開始時間設為左端點,結束時間設為右端點 ,時間段設為區間

步驟

1.將所有區間依照左端點,由小到大排序

2.每次判斷一個區間是否能放到某個組裡,如果不能則新開一個組(有著最小右端點的組的所有區間的最右端點>當前區間左端點,則代表有交集,需新開一個組)

證明(夾擠定理) ans>=cnt 且 ans<=cnt 則 ans=cnt

設ans為最優解,cnt為算法算出來的解

(ans<=cnt)

由於ans是最優解,所以ans<=cnt成立

(ans>=cnt)

1.和有著最小右端點的組有交集代表和所有區間都有交集,因為區間是用左端點由小到大排序的

2.會有第cnt個區間表示必然和前面的所有組有交集,也就是能夠從所有前cnt-1的組裡找到和第cnt組有交集的區間,所以如果要分組,這cnt個區間必然在不同組

,所以至少要有cnt個區間,所以ans>=cnt成立