Python 3 - maximum overlapping interval
This is very similar to the maximum overlapping interval problems. Given a couple of intervals, find the maximum overlapping section. \n\nTo translate into that
This is very similar to the maximum overlapping interval problems. Given a couple of intervals, find the maximum overlapping section. \n\nTo translate into that problem, you have to know for any index i and element a in A, there are 2 cases:\n1. a > i, then shifting to the left will still have a > i, until we wrap around - where you have to consider again.\n2. a <= i, then shifting to the left will have a stop point, where beyond this point we have a > i. However, when you wrap around, you know we still have a <= i, since wrapping around will have a larger i.\n\nIn both cases, you can identify the intervals where a <= i. For each element, we have such intervals. Then we can determine the maximum overlap.\n\nIn the program you can find the 2 cases, respectively. I use events to record the interval boundaries. `(s, 1)` means an interval has a closed left boundary starting at s; `(e, -1)` means an interval has an open right boundary ending at e. \n\n```python\nclass Solution:\n    def bestRotation(self, A: List[int]) -> int:\n        n = len(A)\n        events = []\n        for i, a in enumerate(A):\n            if a > i:\n                events += (i + 1, 1),\n                events += (n - a + i + 1, -1),\n            else:\n                events += (0, 1),\n                events += (i - a + 1, -1),\n                events += (i + 1, 1),\n                events += (n, -1),\n        \n        events.sort()\n        max_score = cur = 0\n        K = -1\n        for e, i in events:\n            cur += i\n            if cur > max_score:\n                K = e\n            max_score = max(max_score, cur)\n        return K\n```
[]