POJ 2437 Muddy roads

問題

一直線の道路上にN個のぬかるみがありそれが[s,e)の形で与えられる（s,eは非負整数）。なお与えられる範囲に重複はない。長さKの木板が無数にあり、これらを使ってぬかるみをすべて覆いたい。最小でいくつの木板が必要か。

やりかた

貪欲。
領域の左端から注目している領域をすべて覆うように木板を置く。置いた後の木板の右端が次のぬかるみにかかっていれば、その領域も続いて覆うように木板を置く。これをすべて覆うまで続ける。

以下ソース。

int main(int argc, char **argv){
  int N, K;
  cin >> N >> K;
  vector<pair<int, int> > m;
  for(int i = 0; i < N; i++){
    int l, r; cin >> l >> r;
    m.push_back(make_pair(l, r));
  }
  sort(ALL(m));
  
  int idx, cnt = 0, r = 0;
  for(idx = 0; idx < N;){
    r = m[idx].first;
    int c = (m[idx].second - m[idx].first + K - 1) / K; //領域idxをすべて覆うのに必要な枚数
    cnt += c;
    r += c * K;//領域の右端を移動する
    idx++;
    while(m[idx].first < r && idx < N){//領域の右端が次の領域にかかっていたらその領域も続けて覆う
      c = (m[idx].second - r + K - 1) / K;
      cnt += c;
      r += c * K;
      idx++;
    }
  }
  cout << cnt << endl;
  return 0;
}