# input: L and H integers with L<=H, and a[0..N) array of pairs of# integers, with a[i][0]<a[i][1] for 0 <= i < N and N>=0,# representing closed intervals [a[i][0],a[i][1]] NOT# necessarily covering the closed interval [L,H]## output: an array b[0..M) with indexes of a[0..N) representing a# minimal interval covering of [L,H] with intervals in a; or# an empty array in case a does not cover [L,H]## time complexity O(N) without sorting; O(N log N) with sortingdefmic_wf(L,H,a):a.sort()ans,low,n,ok,N=list(),L,0,True,len(a)whileokandlow<Handn!=N:ok=a[n][0]<=lowbest,n=n,n+1whileokandn!=Nanda[n][0]<=low:ifa[n][1]>a[best][1]:best=nn+=1ans.append(best)low=a[best][1]ok=okandlow>=Hifok==False:ans=list()returnans
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.