JavaScript O(max(n, 2 * limit)) Merge Intervals
Intuition\nFor each pair, an interval exists, in which a sum needs at most 1 move. And a special that equals the sum of the pair, where a sum needs no move.\n# 
# Intuition\nFor each pair, an interval exists, in which a sum needs at most 1 move. And a special that equals the sum of the pair, where a sum needs no move.\n# Approach\nFor each possible point in the range 2~2*limit, we calculate how many moves are needed. That requires us to do the interval merging task.\n# Complexity\n- Time complexity:\nO(max(n, 2 * limit))\n- Space complexity:\nO(max(n, 2 * limit))\n# Code\n```\n/**\n * @param {number[]} nums\n * @param {number} limit\n * @return {number}\n */\nvar minMoves = function(nums, limit) {\n    const len = nums.length, half = len / 2\n    const minSum = 2, maxSum = 2 * limit\n\n    const pairs = new Array(half)\n    for (let i = 0, j = len - 1; i < j; i++, j--) {\n        const a = nums[i], b = nums[j]\n        const minVal = Math.min(a, b), maxVal = Math.max(a, b)\n        pairs[i] = [minVal, maxVal]\n    }\n\n\n    const ranges = pairs.map(pair => {\n        const [minVal, maxVal] = pair\n        return [minVal + 1, maxVal + limit]\n    })\n\n    function cmp(a, b) {\n        return a - b\n    }\n    const starts = ranges.map(range => range[0]).sort(cmp)\n    const ends = ranges.map(range => range[1]).sort(cmp)\n    const segments = []\n    let prev = 0, layer = 0, j = 0\n    for (let i = 0; i < half; ) {\n        const start = starts[i], end = ends[j]\n        let segment\n        if (start <= end) {\n            segment = [prev, start - 1, layer]\n            prev = start\n            layer++\n            i++\n        } else {\n            segment = [prev, end, layer]\n            prev = end + 1\n            layer--\n            j++\n        }\n        if (segment[2] != 0 && segment[1] >= segment[0])\n            segments.push(segment)\n    }\n    for (; j < half; j++) {\n        const end = ends[j]\n        \n        const segment = [prev, end, layer]\n        prev = end + 1\n        layer--\n        \n        segments.push(segment)\n    }\n\n    \n    const table = new Array(1 + maxSum).fill(0)\n    for (const segment of segments) {\n        const [start, end, count] = segment\n        for (let i = start; i <= end; i++)\n            table[i] = count\n    }\n    for (const pair of pairs) {\n        const sum = pair[0] + pair[1]\n        table[sum]++\n    }\n\n\n    const result = len - Math.max(...table)\n    return result\n};\n```
['JavaScript']