https://atcoder.jp/contests/abc325/tasks/abc325_d
時刻t以上の商品をPriorityQueueに入れます。PriorityQueueは、終了時間が小さいほうから取り出せるようにします。
// Printing Machine #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } //////////////////// Item //////////////////// #[derive(Debug, Copy, Clone, Eq, PartialEq)] struct Item(u64, u64); impl Ord for Item { fn cmp(&self, other: &Self) -> std::cmp::Ordering { other.1.cmp(&self.1) } } impl PartialOrd for Item { fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(other)) } } impl Item { fn read() -> Item { let v: Vec<u64> = read_vec(); Item(v[0], v[0] + v[1]) } } //////////////////// process //////////////////// fn read_input() -> Vec<Item> { let N = read(); let items: Vec<Item> = (0..N).map(|_| Item::read()).collect(); items } fn F(mut items: Vec<Item>) -> usize { let N = items.len(); items.sort_by_key(|a| (a.0, a.1)); let mut counter: usize = 0; let mut t: u64 = 0; let mut k = 0; let mut heap = BinaryHeap::new(); while k < N || !heap.is_empty() { match heap.pop() { None => { t = items[k].0; while k < N && items[k].0 == t { heap.push(items[k]); k += 1 } }, Some(item) => if item.1 >= t { counter += 1; t += 1; while k < N && items[k].0 == t { heap.push(items[k]); k += 1 } } } } counter } fn main() { let goods = read_input(); println!("{}", F(goods)) }