Rust/C++ Sorting
Intuition\n Describe your first thoughts on how to solve this problem. \n1) Sort the items based on prefit.\n2) Pick one item per category in the descending ord
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1) Sort the items based on prefit.\n2) Pick one item per category in the descending order of profit.\n3) While k > 0, picking additional items in the existing categories.\n4) If k == 0, check to see if the smallest item could be replaced with the cost of reducing one category.    \n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n//Rust\nuse std::collections::BTreeSet;\nuse std::collections::HashSet;\n\nimpl Solution {\n    pub fn find_maximum_elegance(items: Vec<Vec<i32>>, k: i32) -> i64 {\n        let mut used = BTreeSet::new();\n        let mut category = HashSet::<i32>::new();\n        let (mut items, mut k) = (items, k);\n        let (mut ret, mut cnt) = (0, 0);\n        \n        items.sort();\n        for i in (0 .. items.len()).rev() {\n            if category.contains(&items[i][1]) { continue }\n            \n            ret += items[i][0] as i64;\n            cnt += 1;\n            used.insert(i);\n            category.insert(items[i][1]);\n            k -= 1;\n            if k == 0 { break } \n        }\n        ret += cnt * cnt;\n\n        for i in (0 .. items.len()).rev() {\n            if used.contains(&i) { continue }\n            \n            if k > 0 {\n                k -= 1;\n                ret += items[i][0] as i64;\n                continue; \n            }\n\n            if let Some(j) = used.iter().next() {\n                let j = *j;\n                if j >= i { break }\n\n                let s = items[i][0] as i64 - items[j][0] as i64;\n                let t = cnt * cnt - (cnt - 1) * (cnt - 1);\n                \n                if s <= t { break }\n                ret += s - t;\n                cnt -= 1;\n                used.remove(&j);\n            }  \n        }\n        \n        ret\n    }\n}\n```\n\n~~~\n// C++\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        sort(items.begin(), items.end());\n        set<int> used;\n        unordered_set<int> category;\n        int cnt = 0, n = items.size();\n        long long ret = 0;\n        \n        for (int i = n - 1; i >= 0; --i) {\n            if (category.find(items[i][1]) != category.end()) continue;\n            category.insert(items[i][1]);\n            ret += items[i][0];\n            used.insert(i);\n            cnt += 1;\n            if (--k == 0) break;\n        } \n        ret += 1LL * cnt * cnt;\n        \n        for (int i = n - 1; i >= 0; --i) {\n            if (used.find(i) != used.end()) continue;\n            \n            if (k > 0) {\n                ret += items[i][0];\n                --k;\n                continue;\n            } \n            \n            int j = *used.begin();\n            if (j >= i) break;\n            long long t = 1LL * cnt * cnt - 1LL * (cnt - 1) * (cnt - 1);\n            if (0LL + items[i][0] - items[j][0] <= t) break;\n                \n            used.erase(j);\n            ret -= t;\n            cnt -= 1;\n            ret += items[i][0] - items[j][0];\n        }\n        \n        return ret;\n    }\n};\n~~~
['Sorting', 'C++', 'Rust']