AtCoder BC103 D: Islands War

問題

https://beta.atcoder.jp/contests/abc103/tasks/abc103_d

解法

最初に(a_i, b_i)の組み合わせについて、a→bの順番でソートします。

そして、ソート後の組み合わせについて、昇順に橋を落とす範囲を求めていきます。

その場合、i番目とi+1番目について、以下の4つのケースが考えられます。

ケース1の場合、i番目の条件が達成できればi+1番目は必ず達成されるので、i+1番目は無視することが出来ます。

ケース2の場合、i+1番目の条件を達成することでi番目が達成できるので、落とす橋の範囲を(a_i+1, b_i+1)に更新して次に進みます。

ケース3の場合、落とす橋の範囲を(a_i+1, b_i)に更新して次に進みます。

ケース4の場合、重なる部分が無いため、落とす橋の数を1増やし、落とす橋の範囲を(a_i+1, b_i+1)に更新して次に進みます。

このようにして、橋を落とす範囲を移動させながら、落とす橋の数を数えていくことで求まります。

実装

n, m = gets.chomp.split.map(&:to_i)
ab = []
m.times do
    ab << gets.chomp.split.map(&:to_i)
end

ab.sort! {|a, b| (a[0] <=> b[0]).nonzero? || (a[1] <=> b[1])}

a = ab[0][0]
b = ab[0][1]
ans = 1
for i in 1..(m-1) do
    if a <= ab[i][0] && ab[i][1] <= b
        a = ab[i][0]
        b = ab[i][1]
    elsif ab[i][0] < b && b <= ab[i][1]
        a = ab[i][0]
    elsif b <= ab[i][0] 
        ans += 1
        a = ab[i][0]
        b = ab[i][1]        
    end
end
puts ans