AtCoder Beginner Contest 325 D

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))
}