網頁

2014年1月18日 星期六

UVa 10020 Minimal Converge

題意:
  數線上有很多條線段,每條線段給左右兩端的座標(L,R),題目問如何用最少的線段去覆蓋[0,M]這個範圍

想法:

  1. 依照L值來排序
  2. 第一次left=0,從a[0]開始找(a[i].L要小於0),找到一個最大R值(Max)的線段a[Max_index]
  3. left=Max_index:下次從這開始找
  4. right=Max
  5. 第二次一樣從left開始找(a[i].L要小於right),找一個最大R值(Max)的線段a[Max_index]
  6. 重複3~5,直到Max大於M