82 lines
2.0 KiB
Rust
82 lines
2.0 KiB
Rust
use std::io::{self, BufRead};
|
|
use std::cmp::Ordering;
|
|
use std::collections::BinaryHeap;
|
|
use std::fmt;
|
|
|
|
struct Meeting {
|
|
start: u32,
|
|
end: u32,
|
|
}
|
|
|
|
impl PartialOrd for Meeting{
|
|
fn partial_cmp(&self, other: &Meeting) -> Option<Ordering>{
|
|
Some(other.end.partial_cmp(&self.end).unwrap().
|
|
then(other.start.partial_cmp(&self.start).unwrap()))
|
|
}
|
|
}
|
|
|
|
impl PartialEq for Meeting{
|
|
fn eq(&self, other: &Meeting) -> bool{
|
|
self.end == other.end
|
|
}
|
|
}
|
|
|
|
impl Ord for Meeting{
|
|
fn cmp(&self, other: &Meeting) -> Ordering{
|
|
other.end.cmp(&self.end).then(other.start.cmp(&self.start))
|
|
}
|
|
}
|
|
|
|
impl Eq for Meeting {}
|
|
|
|
impl fmt::Display for Meeting{
|
|
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result{
|
|
write!(f, "({}, {})", self.start, self.end)
|
|
}
|
|
}
|
|
|
|
impl Meeting{
|
|
fn new(start: u32, end: u32) -> Meeting{
|
|
Meeting{
|
|
start,
|
|
end,
|
|
}
|
|
}
|
|
}
|
|
|
|
fn main(){
|
|
let stdin = io::stdin();
|
|
let mut lock = stdin.lock();
|
|
|
|
let mut line = String::new();
|
|
lock.read_line(&mut line).expect("Failed to read line");
|
|
let n = line.trim().parse::<usize>().expect("Not an integer");
|
|
|
|
let mut heap : BinaryHeap<Meeting> = BinaryHeap::new();
|
|
for (idx, line) in lock.lines().enumerate(){
|
|
if idx == n{
|
|
break;
|
|
}
|
|
let line = line.unwrap();
|
|
let mut line = line.trim().split(" ");
|
|
let start = line.next().expect("Not enough input")
|
|
.parse::<u32>().expect("Not an integer");
|
|
let end = line.next().expect("Not enough input")
|
|
.parse::<u32>().expect("Not an integer");
|
|
let meet = Meeting::new(start, end);
|
|
heap.push(meet);
|
|
}
|
|
|
|
let mut max_num = 0;
|
|
let mut limit = 0;
|
|
while !heap.is_empty(){
|
|
let meet = heap.pop().unwrap();
|
|
if meet.start >= limit{
|
|
max_num += 1;
|
|
limit = meet.end;
|
|
}
|
|
}
|
|
|
|
println!("{}", max_num);
|
|
}
|