Rustで貪欲法 (2)

『アルゴリズムとデータ構造』を Rust で実装してみるシリーズ。7章の貪欲法。

前回 → https://quantized-cube.com/rust-greedy-01

今回は区間スケジューリング問題。

use proconio::input;

// 区間を (i64, i64) で表す
type Interval = (i64, i64);

fn input(use_default_values: bool) -> (usize, Vec<Interval>) {
    if use_default_values {
        let n = 6;
        let inter = vec![(9, 16), (11, 15), (19, 23), (10, 12), (14, 18), (13, 19)];
        return (n, inter);
    } else {
        println!("Input n and inter:");
        input! {
            n: usize,
            inter: [(i64, i64); n],
        }
        return (n, inter);
    }
}

/// 区間スケジューリング問題に対する貪欲法
pub fn code_7_2(use_default_values: bool) -> usize {
    // 入力
    let (n, mut inter) = input(use_default_values);

    // 終端時刻が早い順にソートする
    // inter.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
    inter.sort_by_key(|a| a.1);

    // 貪欲に選ぶ
    let mut res = 0;
    let mut current_end_time = 0;
    for i in 0..n {
        // 最後に選んだ区間と被るのは除く
        if inter[i].0 < current_end_time {
            continue;
        }

        res += 1;
        current_end_time = inter[i].1;
    }
    res
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn code_7_2_works() {
        assert_eq!(code_7_2(true), 3);
    }
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust