[Python] Maximum Overlapping Intervals - with example
html5\n<b>Time Complexity: O(n)</b>\n<b>Space Complexity: O(n)</b>\n\n\nApproach:\n\n\n\nFind the minimum and maximum number of rotations that will produce 1 po
```html5\n<b>Time Complexity: O(n)</b>\n<b>Space Complexity: O(n)</b>\n```\n\n<b>Approach:</b>\n\n<details>\n\n<summary>Find the minimum and maximum number of rotations that will produce 1 point: (click for example)</summary>\n\n```html5\nA = [2, 3, 1, 4, 0]\n    [2, 3, 1, 4, 0]     0 rotations\n    [3, 1, 4, 0, 2]     1 rotation  <b>2 gets a point</b>\n    [1, 4, 0, 2, 3]     2 rotations <b>2 gets a point</b>\n    [4, 0, 2, 3, 1]     3 rotations <b>2 gets a point</b>\n    [0, 2, 3, 1, 4]     4 rotations\n\n2 gets a point for 1, 2, or 3 rotations so add the interval [1, 3] to intervals\n```\n\n</details>\n\n<details>\n\n<summary>Repeat this for the remaining numbers in A: (show intervals)</summary>\n\n```html5\n               2       3       1       1       4       0\nintervals = [[1, 3], [2, 3], [0, 1], [3, 4], [4, 4], [0, 4]]\n```\n\n</details>\n\n<details>\n\n<summary>Use a linescan method to sum how many points each number of rotations will yield in O(n) time: (click to see example)</summary>\n\n```html5\n            0  1  2  3   4      rotations\nlinescan = [0, 0, 0, 0,  0,  0]\n           [0, 1, 0, 0, -1,  0] added interval [1, 3] ; +1 (at index 1) for start at index 1 and -1 (at index 4) for end at index 3\n           [0, 1, 1, 0, -2,  0] added [2, 3]\n           [1, 1, 0, 0, -2,  0] added [0, 1]\n           [1, 1, 0, 1, -2, -1] added [3, 4]\n           [1, 1, 0, 1, -1, -2] added [4, 4]\n           [2, 1, 0, 1, -1, -3] added [0, 4]\n```\t\t   \n\n</details>\n\n<details>\n\n<summary>Convert linescan to a prefix sum array: (show prefix sum array) </summary>\n\n```html5\nlinescan = [2, 1, 0, 1, -1, -3]\npresum  =  [2, 3, 3, 4,  3,  0]  maximum is 4 located at index 3\n```\n\n</details>\n\nWhich means that the highest score is 4 and it occurs at 3 rotations.  \n\n<br>\n\t\t   \n```python\ndef bestRotation(self, A: List[int]) -> int:\n\n\t# 1. For each index, find the range of rotation (k) values that will result in a point\n\tN = len(A)\n\tintervals = []\n\tfor i in range(len(A)):\n\t\tmini = i + 1\n\t\tmaxi = N - A[i] + mini - 1\n\t\tif A[i] > i:\n\t\t\tintervals.append([mini, maxi])\n\t\telse:\n\t\t\tintervals.append([0, i - A[i]])\n\t\t\tintervals.append([mini, N - A[i] + mini])\n\n\t# 2 Calculate how many points each number of rotations will achieve.\n\t#   linescan[3] = 5 means 3 rotations will yield 5 points\n\tlinescan = [0]*N\n\tfor s,e in intervals:\n\t\tif s < N:\n\t\t\tlinescan[s] += 1 if s < N else 0\n\t\tif e + 1 < N:\n\t\t\tlinescan[e + 1] -= 1 if e + 1 < N else 0\n\n\tfor i in range(1, len(linescan)):\n\t\tlinescan[i] += linescan[i-1]\n\n\t# 3. Return the rotations that will produce the most points\n\treturn max(range(N), key = lambda i: (linescan[i], -i))\n```
[]