[GoLang] Greedy, Sorting
Intuition\nIt requires greedy approach. DP hits the time limit.\n\n# Approach\nSort both lists so that:\n\nreward1[i]-reward2[i] > reward1[i+1]-reward2[i+1]\n\n
# Intuition\nIt requires greedy approach. DP hits the time limit.\n\n# Approach\nSort both lists so that:\n```\nreward1[i]-reward2[i] > reward1[i+1]-reward2[i+1]\n```\nNow the left part of `reward1` have the best rewards if the first mouse eats the cheese.\nTake the first `k` elements from `reward1`, and last remaining `n-k` elements from `reward2`.\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\nSorting lists\n\n- Space complexity: $$O(1)$$\n\n# Code\n```\ntype S struct {\n    reward1, reward2 []int\n}\nfunc (s S) Len() int {\n    return len(s.reward1)\n}\nfunc (s S) Swap(i, j int) {\n    s.reward1[i], s.reward1[j] = s.reward1[j], s.reward1[i]\n    s.reward2[i], s.reward2[j] = s.reward2[j], s.reward2[i]\n}\nfunc (s S) Less(i, j int) bool {\n    return s.reward1[i] - s.reward2[i] > s.reward1[j] - s.reward2[j]\n}\n\nfunc miceAndCheese(reward1 []int, reward2 []int, k int) int {\n    sort.Sort(S{reward1, reward2})\n\n    result := 0\n    for _, r := range reward1[:k] {\n        result += r\n    }\n    for _, r := range reward2[k:] {\n        result += r\n    }\n    return result\n}\n\n```
['Greedy', 'Sorting', 'Go']