Solution

Memo

  • 그리디는 매번 반복하지만, 그리디로 풀린다는 감각을 갖는게 어렵고 헷갈리는 것 같다.
  • 대신 확실해지면 구현은 쉽다.
  • 종료시간, 시작시간 순으로 스케줄을 정렬하고
  • 종료시간이 가장 빠른 순으로 마지막 원소와 valid하여 결과에 추가, 마지막으로 결과 배열을 반환한다.
// Baekjoon - 1931
// https://www.acmicpc.net/problem/1931

use std::io::{self, Read, Write};

fn main() {
    let mut stdin = io::stdin().lock();
    let mut stdout = io::stdout().lock();
    let mut input = String::new();
    stdin.read_to_string(&mut input).unwrap();
    let mut lines = input.lines();

    let n: usize = lines.next().unwrap().parse().unwrap();
    let mut schedules: Vec<(usize, usize)> = vec![];

    for i in 0..n {
        let tmp: Vec<usize> = lines.next().unwrap().split_whitespace().map(|x| x.parse().unwrap()).collect();
        schedules.push((tmp[0], tmp[1]));
    }

    schedules.sort_by(|a, b| {
        a.1.cmp(&b.1).then_with(|| a.0.cmp(&b.0))
    });

    let mut result: Vec<(usize, usize)> = vec![];
    result.push(schedules[0]);

    for i in 1..n {
        let tmp = schedules[i];
        let former = result.last().unwrap();

        if tmp.0 >= former.1 {
            result.push(tmp);
        }
    }

    let output = result.len();
    write!(stdout, "{}", output).unwrap();
}