ABC103-D:Islands War(400)
問題
https://beta.atcoder.jp/contests/abc103/tasks/abc103_d
N 頂点と N-1 本の橋がある。 N-1 本の橋は i と i+1 を結ぶ。与えられる M つの要望を満たすようにするためには、最小でいくつの橋を除けばいいか。
制約
- 1 <= N <= 105
- 1 <= M <= 105
- 1 <= a_i, b_i < N
- (a_i, b_i) はすべて異なる
考え方
グラフの問題のように見えるが、橋がすべて i と i+1 を結んでいるので、数直線で考えてよい。すると M つの要望は区間が与えられていることがわかる。
サンプル2 を例に考えていこう。M 個の区間が与えられて、オレンジの縦線で各区間を切断するとき、最小の縦線は何本であるかということである。
区間 [a_i, b_i), [a_j, b_j) (i < j)の2つの区間を同時に切断したいとする時、最適な解は切断方法は b_i の直前の区間を含むように切断するのが最適である。仮に a_j < b_i であれば同時に切断できるためである。もともと a_j >= b_i である時はどのようにしても同時に切断することはできない。
よって、すべての区間を b で昇順にソートして、各 a_j が b_i 未満であるかチェックすればいい。 b_i 未満であれば同時に切断でき、できないときは新たに b_j の直前の区間で切断する。
public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(), m = in.nextInt(); P[] ps = new P[m]; for (int i = 0; i < m; i++) { int a = in.nextInt(), b = in.nextInt(); ps[i] = new P(a, b); } Arrays.sort(ps); int s = 0, count = 0;; for (int i = 0; i < m; i++) { if (s < ps[i].b) { s = ps[i].b; count++; } } out.println(count); } class P implements Comparable<P> { int a, b; public P(int a, int b) { super(); this.a = a; this.b = b; } @Override public int compareTo(P o) { if (this.b == o.b) { return this.a - o.a; } else { return this.b - o.b; } } }