Introduction

In this blog post, we will explore how to solve the LeetCode problem "3414" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You are given a 2D integer array intervals, where intervals[i] = [li, ri, weighti]. Interval i starts at position li and ends at ri, and has a weight of weighti. You can choose up to 4 non-overlapping intervals. The score of the chosen intervals is defined as the total sum of their weights. Return the lexicographically smallest array of at most 4 indices from intervals with maximum score, representing your choice of non-overlapping intervals. Two intervals are said to be non-overlapping if they do not share any points. In particular, intervals sharing a left or right boundary are considered overlapping. Example 1: Input: intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]] Output: [2,3] Explanation: You can choose the intervals with indices 2, and 3 with respective weights of 5, and 3. Example 2: Input: intervals = [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]] Output: [1,3,5,6] Explanation: You can choose the intervals with indices 1, 3, 5, and 6 with respective weights of 7, 6, 3, and 5. Constraints: 1 <= intevals.length <= 5 * 104 intervals[i].length == 3 intervals[i] = [li, ri, weighti] 1 <= li <= ri <= 109 1 <= weighti <= 109

Explanation

Here's the breakdown of the approach, complexity, and the Python code solution:

• High-Level Approach:

  • Dynamic Programming: Use DP to store the maximum score achievable by selecting up to k (1 to 4) intervals ending at a particular index.
  • Binary Search: Efficiently find the non-overlapping interval that ends before the current interval begins.
  • Lexicographical Ordering: Maintain the indices of the intervals chosen during DP and choose the lexicographically smallest among the solutions with maximum score.

• Complexity:

  • Runtime Complexity: O(N log N), where N is the number of intervals. The log N factor comes from binary search.
  • Storage Complexity: O(N)

Code

    def solve():
    intervals = [[1,3,2],[4,5,2],[1,5,5],[6,9,3],[6,7,1],[8,9,1]]
    # intervals = [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]
    n = len(intervals)

    # Sort intervals by end time. If end times are same, sort by start time.
    indexed_intervals = sorted([(r, l, w, i) for i, (l, r, w) in enumerate(intervals)])  # (end, start, weight, index)
    endpoints = [r for r, _, _, _ in indexed_intervals]

    dp = {} # dp[k][i] stores the max score with at most k intervals ending at i
    path = {} # path[k][i] stores the index of the previous interval in the optimal solution

    def get_max_score(k, i):
        if k == 0:
            return 0, []
        if i < 0:
            return float('-inf'), []

        if (k, i) in dp:
            return dp[(k, i)], path[(k, i)]

        # Option 1: Don't include the current interval
        score1, path1 = get_max_score(k, i - 1)

        # Option 2: Include the current interval
        _, start, weight, index = indexed_intervals[i]

        # Find the latest non-overlapping interval
        j = -1
        l, r = 0, i - 1
        while l <= r:
            mid = (l + r) // 2
            if indexed_intervals[mid][0] < start:
                j = mid
                l = mid + 1
            else:
                r = mid - 1

        score2, path2 = get_max_score(k - 1, j)
        score2 += weight
        path2 = path2 + [index]

        if score2 > score1:
            dp[(k, i)] = score2
            path[(k, i)] = path2
            return score2, path2
        elif score2 == score1:
            if len(path2) > 0 and len(path1) > 0 and path2 < path1: # compare path lexicographically.
                dp[(k, i)] = score2
                path[(k, i)] = path2
                return score2, path2
            else:
                dp[(k, i)] = score1
                path[(k, i)] = path1
                return score1, path1
        else:
            dp[(k, i)] = score1
            path[(k, i)] = path1
            return score1, path1

    best_score = float('-inf')
    best_path = []
    for k in range(1, 5):
        score, cur_path = get_max_score(k, n - 1)
        if score > best_score:
            best_score = score
            best_path = cur_path
        elif score == best_score and len(cur_path) > 0 and len(best_path) > 0 and cur_path < best_path: # compare path lexicographically
            best_path = cur_path

    best_path.sort()
    print(best_path)

solve()