FP: Single expression, 7 lines, 196ms, beats 100%. Sort, scan, to SortedMap, look up queries in map
Intuition\nSort by price, walk the array assigning each price the maximum beauty found so far.\n\nLook up each query in a sorted map of (price, beauty). \n\nThe
# Intuition\nSort by price, walk the array assigning each price the maximum beauty found so far.\n\nLook up each query in a sorted map of (price, beauty). \n\nThe sorted map allows us to find the greatest key less than or equal to the query: this key\'s value is the maximum beauty for the query.\n\n# Approach\nSort the (price, beauty) pairs by price ascending, beauty descending: this orders the prices from lowest to highhesy, and within each price, the first beauty is the ximum for that price.\n\nScan over the sorted pairs, and for each, map it to a pair of (price, maximum beauty seen so far). This is why within each price, the maximum beauty for that price comes first.\n\nSince the list returned by scan starts with scan\'s seed value, which we make Pair(0, 0), this ensures we return zero for a query less than the minimum price.\n\nTurn the pairs into a Map, then turn the Map into a SortedMap.\n\nFor each query, get the headMap for the query plus 1, and take the headMap\'s maximum key. This gives us the maximum key less than or equal to the query.\n\nMap the query to the value of that key.\n\n# Complexity\n- Time complexity:\n$$O(n*log(n)) + O(m * log (n))$$ \n\n- Space complexity:\n$$O(n + m)$$ \n\n# Code\n```kotlin []\nclass Solution {\n    fun maximumBeauty(items: Array<IntArray>, queries: IntArray): IntArray {\n        return items\n            .sortedWith(compareBy({ it[0] }, { -it[1] }))\n            .scan(Pair(0, 0)) { (a1, a2), (e1, e2) -> Pair(e1, max(a2, e2)) }\n            .toMap()\n            // or we could .associate { it }\n            .toSortedMap()\n            .let { m -> queries.map { m[m.headMap(it + 1).lastKey()]!! }}\n            .toIntArray()\n    }\n}\n```
['Ordered Map', 'Sorting', 'Kotlin']