ソートと貪欲法

読了目安 約3分

sorted(by:) で並べ替え、終了時刻順の貪欲法で区間スケジューリングを解く。

多くの問題は、データを並べ替えるだけで見通しが良くなります。 Swift の並べ替えは sorted() を呼ぶだけです。

sorted() と sorted(by:)

sorted() は、昇順に並べ替えた新しい配列を返します。 並べ方を変えたいときは、sorted(by:) にクロージャで比較を渡します。 比較は「左を前に置きたいとき true」を返すのがルールです。

let a = [59, 26, 53, 97, 41]
print(a.sorted())
print(a.sorted(by: >))

let items = [(name: "りんご", price: 240), (name: "バナナ", price: 120), (name: "メロン", price: 600)]
for item in items.sorted(by: { $0.price < $1.price }) {
    print(item.name, item.price)
}

試してみよう: 値段の比較を > に変えて、高い順に並ぶことを確かめてください。

ソートすると何が嬉しいか

ソートしておくと、次のような手が使えるようになります。

• 最小値と最大値が両端に来る
• 同じ値が隣どうしに集まる
• 二分探索が使えるようになる
• 「良いものから順に処理する」方針が 1 本のループで書ける

最後の「良いものから順に処理する」には名前が付いています。 その時点で最も良く見える選択を繰り返す方法を貪欲法と呼びます。 貪欲法はいつでも正しいわけではないので、その選び方で損をしない根拠を問題ごとに確かめます。

区間スケジューリング

貪欲法の代表例が区間スケジューリングです。 N 個の仕事に開始時刻と終了時刻があり、時間が重ならないように最大何個選べるかを求めます。

解法は、終了時刻が早い順にソートし、前に選んだ仕事と重ならない仕事を順に選ぶだけです。 終了が最も早い仕事を選んでも損をしません。 残りの仕事に使える時間が最も長く残るからです。

let jobs = [(s: 2, e: 5), (s: 1, e: 3), (s: 6, e: 9), (s: 4, e: 7)]

var count = 0
var lastEnd = 0
for job in jobs.sorted(by: { $0.e < $1.e }) {
    if job.s >= lastEnd {
        count += 1
        lastEnd = job.e
        print("選ぶ: \(job.s) 時から \(job.e) 時")
    }
}
print("最大 \(count) 個")

計算量

sorted() と sorted(by:) は O(N log N) です。 選ぶループは O(N) なので、全体も O(N log N) に収まります。 N が 10 万でも一瞬で終わります。

学びどころ

演習

N 個の仕事があります。 i 番目の仕事は時刻 S_i に始まり、時刻 E_i に終わります。 時間が重ならないように選べる仕事の最大数を出力してください。

前の仕事の終了時刻と次の仕事の開始時刻が同じ場合は、重なっていないとみなします。

入力は 1 行目に N、続く N 行に S_i と E_i が空白区切りです。

制約: 1 ≤ N ≤ 100000、0 ≤ S_i < E_i ≤ 1000000000。

入力例:
3
1 3
2 5
4 7

出力例:
2

let n = Int(readLine()!)!
var jobs: [(s: Int, e: Int)] = []
for _ in 0..<n {
    let p = readLine()!.split(separator: " ").map { Int($0)! }
    jobs.append((s: p[0], e: p[1]))
}

var count = 0
var lastEnd = 0
for job in jobs.sorted(by: { $0.e < $1.e }) {
    if job.s >= lastEnd {
        count += 1
        lastEnd = job.e
    }
}
print(count)