Python, schedule interval problem
For an item in the array, regardless of where it is, we know where are the indexes that makes it gain "1" point. These indexes are continuous. We can convert th
For an item in the array, regardless of where it is, we know where are the indexes that makes it gain "1" point. These indexes are continuous. We can convert these indexes to desired shifting range of "k", which is also continuous. Now this problem becomes a schedule interval problem: "We know the time schedules of every person, we want to find out the time that every one is free." (in this question we want to find the time that most people are not free)  \nHere "k" is time point in schedule, "k" range is the desired schedule interval, the "k" that makes the biggest overlap is the answer.\n\n```\nclass Solution:\n    def bestRotation(self, A: List[int]) -> int:\n        n=len(A)\n        events=[0]*(n+1)\n        for i,v in enumerate(A):\n            start,end=v,n-1\n            k3=k4=0\n            if end>=start:\n                if i>=end:\n                    k1,k2=i-end,i-start\n                    events[k1]+=1\n                    events[k2+1]-=1\n                elif i>=start:\n                    k1,k2=0,i-start\n                    k3,k4=n-(end-i),n-1\n                    events[k1]+=1\n                    events[k2+1]-=1\n                    events[k3]+=1\n                    events[k4+1]-=1\n                else:\n                    k1,k2=n-(end-i),n-(start-i)\n                    events[k1]+=1\n                    events[k2+1]-=1\n        cur=maxpt=res=0\n        for k,flg in enumerate(events):\n            cur+=flg\n            if cur>maxpt:\n                res=k\n                maxpt=cur\n        return res\n```
[]