Rust with sort, dedup & partition_point | 9ms, beats 100%
Intuition\nIf we sort the items by price (ascending) and then remove all the items for which the beauty is not higher than the previous highest beauty we can us
# Intuition\nIf we sort the items by price (ascending) and then remove all the items for which the beauty is not higher than the previous highest beauty we can use binary search.\n\n# Code\n```rust []\nimpl Solution {\n    pub fn maximum_beauty(mut items: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {\n        items.sort_unstable();\n        items.dedup_by(|right, left| right[1] <= left[1]);\n        queries.into_iter().map(|q|\n            match items.partition_point(|it| it[0] <= q) {\n                0 => 0,\n                i => items[i - 1][1]\n            }\n        ).collect()\n    }\n}\n```\n\n# Implementation notes\n* We don\'t need to use a key for sorting because the default comparison for `Vec` does elementwise comparison (starting from the price, which is what we want to sort by).\n* `.sort_unstable()` is typically a bit faster than `.sort()`.\n* After sorting the `.dedup_by(F)` method can be used to remove items for which there exists a cheaper item with the same or higher beauty to the left of it. Note that the elements are passed to `F` in opposite order from their order in the slice.\n* `partition_point(F)` uses binary search to find the first index for which the predicate `F` returns *false* (all elements for which `F` returns true must be at the start of the slice) so we need to subtract one from it to find the last element for which it returned *true*.\n\n# Complexity\n- Time complexity: $O((N + M) \\log M)$ where $N$ is the number of queries, and $M$ is the length of items\n\n- Space complexity: $O(N)$\n
['Array', 'Binary Search', 'Sorting', 'Rust']