[Python 3] Intervals
Intuition\n1. Solve problem if the question was to calculate the sum of shortest distances between all pairs of houses\n2. Transform all subsums into intervals 
# Intuition\n1. Solve problem if the question was to calculate the sum of shortest distances between all pairs of houses\n2. Transform all subsums into intervals and add up them efficiently\n\n# Approach\n* For each start node calculate the sum of shortest distances to each other node\n* Transform each subsum into interval (tuple) `(distance to current node, how many steps to make)`\n* Add up intervals efficiently\n  * Sort intervals\n  * Store heap of currently active intervals (key to heap is distance when this interval will be passed)\n  * Increment distance and add the number of currently active intervals (length of heap) to the corresponding answer (ans[distance])\n\n# Complexity\n- Time complexity: $$O(n\\log n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```python\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        intervals = []\n        # [(distance to current node, how many steps to make)]\n        # e.g. if we are DIST edges from start and want to jump JUMPS times\n        # then interval would look like (DIST, JUMPS)\n        def add_interval(cur, edge_cnt):\n            if edge_cnt == 0: return\n            intervals.append((cur, edge_cnt))\n            # if we had to calculate the sum of all distances\n            # this function would be equal to\n            # ans += (cur+1 + cur+edge_cnt) * edge_cnt // 2\n\n        if x > y:\n            x, y = y, x\n        \n        # * - * - * - X - * - * - Y - * - * - *\n        #     ^zone1      ^zone2      ^zone3\n        zone1 = x-1\n        zone2 = y-x\n        zone3 = n-y\n    \n        def handle_zone1_start(i):\n            add_interval(0, i-1)\n            add_interval(0, x-i)\n            cur = x-i\n            # reached x\n\n            if x != y:\n                edges_left = zone2-2\n                add_interval(cur, (edges_left//2) + 1)\n                add_interval(cur, (edges_left//2) + 1)\n                if edges_left & 1:\n                    add_interval(cur+1+edges_left//2, 1)\n                cur += 1\n            # reached y\n            \n            add_interval(cur, zone3)\n            \n        def handle_zone2_start(i):\n            tox = i-x  # distance to x\n            toy = y-i  # distance to y\n            nearest = min(tox, toy)\n            edges_left = max(tox, toy) - nearest\n            add_interval(0, nearest + (edges_left//2))\n            add_interval(0, nearest + (edges_left//2))\n            if edges_left & 1:\n                add_interval(nearest + (edges_left//2), 1)\n\n            tox = min(tox, toy+1)\n            toy = min(toy, tox+1)\n            # reached x, y\n            \n            add_interval(tox, zone1)\n            add_interval(toy, zone3)\n    \n        def handle_zone3_start(i):\n            add_interval(0, n-i)\n            add_interval(0, i-y)\n            cur = i-y\n            # reached y\n\n            if x != y:\n                edges_left = zone2-2\n                add_interval(cur, (edges_left//2) + 1)\n                add_interval(cur, (edges_left//2) + 1)\n                if edges_left & 1:\n                    add_interval(cur+1+edges_left//2, 1)\n                cur += 1\n            # reached x\n            \n            add_interval(cur, zone1)\n\n\n        for i in range(1, n+1):\n            if i <= x:\n                handle_zone1_start(i)\n            elif x < i < y:\n                handle_zone2_start(i)\n            else:\n                handle_zone3_start(i)\n\n        ans = [0]*n\n        intervals.sort(key=lambda i: (i[0],-i[1]))\n        h = []\n        step = 0\n        def make_step():\n            nonlocal step, ans, h\n            step += 1\n            ans[step-1] += len(h)\n            while h and h[0] <= step:\n                heapq.heappop(h) \n\n        for i in range(len(intervals)-1):\n            cur, edge_cnt = intervals[i]\n            heapq.heappush(h, step+edge_cnt)\n            next_step = intervals[i+1][0]\n            while step < next_step:\n                make_step()\n        cur, edge_cnt = intervals[-1]\n        heapq.heappush(h, step+edge_cnt)\n        while h:\n            make_step()\n\n        return ans\n\n```
['Sorting', 'Heap (Priority Queue)', 'Python3']