leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

2070-most-beautiful-item-for-each-query.rs (3392B)

      1use leetcode::*;
      2/// 2070. Most Beautiful Item for Each Query (Medium)
      3///
      4/// You are given a 2D integer array items where items[i] = [pricei, beautyi]
      5/// denotes the *price* and *beauty* of an item respectively.
      6///
      7/// You are also given a *0-indexed* integer array queries. For each queries[j],
      8/// you want to determine the *maximum beauty* of an item whose *price* is *less
      9/// than or equal* to queries[j]. If no such item exists, then the answer to
     10/// this query is 0.
     11///
     12/// Return an array answer of the same length as queries where answer[j] is the
     13/// answer to the jth query.
     14///
     15/// *Example 1:*
     16///
     17///   *Input:* items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
     18///   *Output:* [2,4,5,5,6,6]
     19///   *Explanation:*
     20///   - For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the
     21///     answer for this query is 2.
     22///   - For queries[1]=2, the items which can be considered are [1,2] and [2,4].
     23///     The maximum beauty among them is 4.
     24///   - For queries[2]=3 and queries[3]=4, the items which can be considered are
     25///     [1,2], [3,2], [2,4], and [3,5].
     26///     The maximum beauty among them is 5.
     27///   - For queries[4]=5 and queries[5]=6, all items can be considered.
     28///     Hence, the answer for them is the maximum beauty of all items, i.e., 6.
     29///
     30/// *Example 2:*
     31///
     32///   *Input:* items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
     33///   *Output:* [4]
     34///   *Explanation:*
     35///   The price of every item is equal to 1, so we choose the item with the
     36///   maximum beauty 4.
     37///   Note that multiple items can have the same price and/or beauty.
     38///
     39/// *Example 3:*
     40///
     41///   *Input:* items = [[10,1000]], queries = [5]
     42///   *Output:* [0]
     43///   *Explanation:*
     44///   No item has a price less than or equal to 5, so no item can be chosen.
     45///   Hence, the answer to the query is 0.
     46///
     47/// *Constraints:*
     48///
     49///   * 1 <= items.length, queries.length <= 105
     50///   * items[i].length == 2
     51///   * 1 <= pricei, beautyi, queries[j] <= 109
     52///
     53use std::cmp;
     54
     55struct Solution {}
     56
     57impl Solution {
     58    pub fn maximum_beauty(mut items: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
     59        let mut queries = queries.into_iter().enumerate().collect::<Vec<_>>();
     60        items.sort_by(|a, b| a[0].cmp(&b[0]));
     61        queries.sort_by(|(_ia, a), (_ib, b)| a.cmp(b));
     62        let mut answers = vec![0i32; queries.len()];
     63        let mut iter = items.iter().peekable();
     64        let mut best = 0i32;
     65        for (i, q) in queries {
     66            while let Some(item) = iter.peek() {
     67                if item[0] > q {
     68                    break;
     69                }
     70                best = cmp::max(best, item[1]);
     71                iter.next();
     72            }
     73            answers[i] = best
     74        }
     75        answers
     76    }
     77}
     78
     79pub fn main() {
     80    println!("{:?}", Solution::maximum_beauty(arg_into(1), arg_into(2)))
     81}
     82
     83#[cfg(test)]
     84mod tests {
     85    use crate::Solution;
     86    use leetcode::{vi, vvi};
     87
     88    #[test]
     89    fn test() {
     90        assert_eq!(
     91            Solution::maximum_beauty(vvi("[[1,2],[3,2],[2,4],[5,6],[3,5]]"), vi("[1,2,3,4,5,6]")),
     92            vi("[2,4,5,5,6,6]")
     93        );
     94        assert_eq!(
     95            Solution::maximum_beauty(vvi("[[1,2],[1,2],[1,3],[1,4]]"), vi("[1]")),
     96            vi("[4]")
     97        );
     98        assert_eq!(
     99            Solution::maximum_beauty(vvi("[[10,1000]]"), vi("[5]")),
    100            vi("[0]")
    101        );
    102    }
    103}