Problem statement

https://binarysearch.com/problems/Take-All/

Solution

First of all notice, tha what is asked in this problem is find the cheapest union of segments, such that after we remove repetitions we have segment [0, N-1] This problem have several ideas how you can solve it:

  1. Let us define by dp[i] the minimum cost to cover [0, i] segment. Then how we can calculate dp[i]? Imagine, that current segment is [s, e]. Then we need to look at all segments [s1, e1], such that e1 >= s-1, that is we can connect them. How we can choose the best of them, because potentiall there can be O(n) candidates and this will lead to O(n^2) complexity?

The clue idea is to keep the heap of candidates, where they are sorted by key dp[e1] + prefix[e1], where prexix[e1] is what cost we need to pay to remove elements upty e1. Why we use this key? Imagine that we have two candidates [s1, e1] and [s2, e2], which one to choose? We compare dp[e1] + prefix[e1] and dp[e2] + prefix[e2] and choose the smallest one: in the first one we have prefix[s:e1] term and in second we have prefix[s:e2] term which we pay for.

Complexity

Time complexity is O(n log n), space is O(n).

Code

class Solution:
    def solve(self, A, B):
        n = len(B)
        A.sort()

        acc = list(accumulate(B))
        dp = [float("inf")] * n
        pq = [(0, -1, 0)]

        for s, e, cost in A:
            while pq and pq[0][1] < s-1: heappop(pq)  #lazy deletion
            if len(pq) == 0: return -1
            p = pq[0]
            dp[e] = min(dp[e], p[2] + cost + (acc[p[1]] - acc[s] + B[s]) * (p[1] >= s))
            heappush(pq, (dp[e] + acc[e], e, dp[e]))

        return dp[-1] if dp[-1] != float("inf") else -1

Solution 2

There is also solution, using graphs! We can see at out problem as finding the shortest path between nodes 0 and n-1, where we allowe to go in positive direction as well as we can make stesp backward with length 1. Why this is true, because for every valid set of segments there will never be a point where 3 points intersect. So, we just use Dijkstra algorithm to find shortest path.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

class Solution:
    def solve(self, A, B):
        n = len(B)

        G = defaultdict(list)
        for s, e, w in A:
            G[s].append([e + 1, w])
        for i, r in enumerate(B):
            G[i + 1].append([i, r])

        dist = [float('inf')] * (n + 1)
        dist[0] = 0
        heap = [(0, 0)]

        while heap:
            min_dist, idx = heappop(heap)
            if idx == n: return min_dist
            for neibh, weight in G[idx]:
                cand = min_dist + weight
                if cand < dist[neibh]:
                    dist[neibh] = cand
                    heappush(heap, (cand, neibh))
                    
        return -1

Remark

There is also solution using monotonic queue + binary search, but I am not sure how it works here. Also there is solution with segment trees, which similar to solution 1, but instead of heaps we use segment tree: we store at index i in our segment tree dp[i] + acc[i], and then we can answer queries fast.