2251. Number of Flowers in Full Bloom Hard

1/**
2 * [2251] Number of Flowers in Full Bloom
3 *
4 * You are given a 0-indexed 2D integer array flowers, where flowers[i] = [starti, endi] means the i^th flower will be in full bloom from starti to endi (inclusive). You are also given a 0-indexed integer array persons of size n, where persons[i] is the time that the i^th person will arrive to see the flowers.
5 * Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the i^th person arrives.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/ex1new.jpg" style="width: 550px; height: 216px;" />
9 * Input: flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
10 * Output: [1,2,2,2]
11 * Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
12 * For each person, we return the number of flowers in full bloom during their arrival.
13 *
14 * Example 2:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/ex2new.jpg" style="width: 450px; height: 195px;" />
16 * Input: flowers = [[1,10],[3,3]], persons = [3,3,2]
17 * Output: [2,2,1]
18 * Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
19 * For each person, we return the number of flowers in full bloom during their arrival.
20 *
21 *  
22 * Constraints:
23 *
24 * 1 <= flowers.length <= 5 * 10^4
25 * flowers[i].length == 2
26 * 1 <= starti <= endi <= 10^9
27 * 1 <= persons.length <= 5 * 10^4
28 * 1 <= persons[i] <= 10^9
29 *
30 */
31use std::cmp::Ordering;
32use std::collections::BinaryHeap;
33use std::collections::HashMap;
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/number-of-flowers-in-full-bloom/
37// discuss: https://leetcode.com/problems/number-of-flowers-in-full-bloom/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41#[derive(Copy, Clone, Eq, PartialEq)]
42pub struct Flower {
43    start: i32,
44    amount: i32,
45}
46impl Ord for Flower {
47    fn cmp(&self, other: &Self) -> Ordering {
48        // Notice that the we flip the ordering on costs.
49        // In case of a tie we compare positions - this step is necessary
50        // to make implementations of `PartialEq` and `Ord` consistent.
51        other.start.cmp(&self.start)
52    }
53}
54// `PartialOrd` needs to be implemented as well.
55impl PartialOrd for Flower {
56    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
57        Some(self.cmp(other))
58    }
59}
60
61impl Solution {
62    pub fn full_bloom_flowers(flowers: Vec<Vec<i32>>, persons: Vec<i32>) -> Vec<i32> {
63        let mut heap = BinaryHeap::new();
64        let mut persons_clone = persons.clone();
65        persons_clone.sort();
66        let mut map: HashMap<i32, i32> = HashMap::new();
67
68        for v in flowers {
69            heap.push(Flower {
70                start: v[0],
71                amount: 1,
72            });
73            heap.push(Flower {
74                start: v[1] + 1,
75                amount: -1,
76            });
77        }
78
79        
80        let mut pre = 0;
81        for person in persons_clone {
82            if map.contains_key(&person) {continue}
83            let mut count = pre;
84            while !heap.is_empty() && heap.peek().unwrap().start <= person {
85                let n = heap.pop().unwrap();
86
87                count += n.amount;
88            }
89            pre = count;
90            map.insert(person, count);
91        }
92
93        let mut result = vec![];
94        for i in persons {
95            result.push(*map.get(&i).unwrap());
96        }
97        result
98    }
99}
100
101// submission codes end
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn test_2251_1() {
109        assert_eq!(
110            Solution::full_bloom_flowers(
111                vec!(vec!(1, 6), vec!(3, 7), vec!(9, 12), vec!(4, 13)),
112                vec!(2, 3, 7, 11)
113            ),
114            vec!(1, 2, 2, 2)
115        );
116        assert_eq!(
117            Solution::full_bloom_flowers(vec!(vec!(1, 10), vec!(3, 3)), vec!(3, 3, 2)),
118            vec!(2, 2, 1)
119        );
120    }
121}
122