[Java] Simple trick - Ranges and Events
Intuition\nLook at the question this way - each num in the array can fall in the range of [num - k, num + k] after change. Need to understand the longest overla
# Intuition\nLook at the question this way - each num in the array can fall in the range of $$[num - k, num + k]$$ after change. Need to understand the longest overlap between these ranges.\nNow the tricks are that we\'re limited by number of operations and some numbers can be left unchanged.\n\n# Approach\nLet\'s focus on 3 key points in each num:\n- range start - we can potentially spend one operation to reach it\n- range mid - we don\'t need an operation\n- range end - everything after that is unreachable\nNow we construct the list of those important points. Then we sort them and traverse.\nAt each point we update:\n- current number we process (var $$pos$$)\n- how many nums can reach it due to operation (var $$current$$)\n- how many nums are similar to their initial values and don\'t require operations (var $$real$$)\n- our result will be all the \'real\' nums plus all the nums that could be transformed ($$Math.min(current, numOperations)$$).\n\n\n# Complexity\n- Time complexity:\n$$O(n*log(n))$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```java []\nclass Solution {\n    public int maxFrequency(int[] nums, int k, int numOperations) {\n        List<long[]> events = new ArrayList<>();\n        for (int i : nums) {\n            events.add(new long[] { i - k, 1 });\n            events.add(new long[] { i, 0 });\n            events.add(new long[] { i + k + 1, -1 });\n        }\n        events.sort((a, b) -> a[0] == b[0] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0]));\n        long res = 0, current = 0, real = 0, pos = 0;\n        for (long[] e : events) {\n            if (e[0] > pos) {\n                current += real;\n                real = 0;\n                pos = e[0];\n            }\n            if (e[1] == 0) {\n                real++;\n                current--;\n            } else {\n                current += e[1];\n            }\n            res = Math.max(res, Math.min(current, numOperations) + real);\n        }\n        return (int) res;\n    }\n}\n```
['Simulation', 'Java']