区間選択アルゴリズム

何を書いているか

区間選択アルゴリズムの備忘録。
C++とGoで記述。
プログラミングスキルチェックの問題で選択アルゴリズムを使って解く問題に出会ったので。

コード

ここでは終わりと次の始まりがつながらない区間を選択するパターン。
つながった場合も選択可能とする場合はコードの示した箇所を等比較にすればよい。

C++版

# include <bits/stdc++.h>
using namespace std;
int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> X(N), L(N);
    for (int i = 0; i < N; i++) {
        cin >> X.at(i) >> L.at(i);
    }

    vector<pair<int, int>> p(N);
    for (int i = 0; i < N; i++) {
        p[i].first = X[i] + L[i]; // 終端を先に入れておく
        p[i].second = X[i];// - L[i];
    }

    sort(p.begin(), p.end()); // 終端を優先にソート
    
    int ans = 1;
    int t = p[0].first; // t:=現在までに選択した区間の中で一番後ろの点
    for (int i = 1; i < N; i++) {
        if (t < p[i].second) { //ここを等記号にすれば区間がつながっていてもOKとする。
            ans++;
            t = p[i].first;
        }
    }

    cout << ans << endl;

    return 0;
}

Go版

package main
import (
    "fmt"
    "sort"
    )

type Pair struct {
    start int
    length int
    end int
}
func main(){
    var N int
    fmt.Scan(&N)
    
    kukan:=make([]Pair,0)
    for i:=0;i<N;i++ {
        var start,length int
        fmt.Scan(&start)
        fmt.Scan(&length)
        kukan=append(kukan, Pair{start, length, start+length})
    }
    
    sort.Slice(kukan, func(i, j int) bool { return kukan[i].end < kukan[j].end })
    
    ans:= 1;
    t:= kukan[0].end; // t:=現在までに選択した区間の中で一番後ろの点
    for i:=1;i<N;i++ {
        if (t < kukan[i].start) {
            ans++
            t=kukan[i].end
        }
    }
    
    fmt.Println(ans)
}