1use crate::util::iter::*;
3use crate::util::parse::*;
4use std::ops::Range;
5
6type Input = (Vec<Range<u64>>, Vec<u64>);
7
8pub fn parse(input: &str) -> Input {
9 let (prefix, suffix) = input.split_once("\n\n").unwrap();
10 let mut ranges: Vec<_> = prefix.iter_unsigned().chunk::<2>().collect();
11 let mut ids: Vec<_> = suffix.iter_unsigned().collect();
12 let mut range = 0..0;
13 let mut merged = Vec::new();
14
15 ranges.sort_unstable();
16 ids.sort_unstable();
17
18 for [from, to] in ranges {
19 if from < range.end {
20 range.end = range.end.max(to + 1);
21 } else {
22 merged.push(range);
23 range = from..to + 1;
24 }
25 }
26
27 merged.push(range);
28 (merged, ids)
29}
30
31pub fn part1(input: &Input) -> usize {
32 let (merged, ids) = input;
33 let position = |id: u64| ids.binary_search(&id).unwrap_or_else(|e| e);
34 merged.iter().map(|range| position(range.end) - position(range.start)).sum()
35}
36
37pub fn part2(input: &Input) -> u64 {
38 let (merged, _) = input;
39 merged.iter().map(|range| range.end - range.start).sum()
40}