Weighted Interval Scheduling

def weighted_interval_scheduling(intervals):
    """
    Weighted interval scheduling using DP.
    intervals: [(start, end, weight), ...]
    Time: O(n log n), Space: O(n)
    """
    n = len(intervals)
    intervals.sort(key=lambda x: x[1])  # Sort by end time
    
    # Find previous non-overlapping interval
    prev = [-1] * n
    for i in range(n):
        start_i = intervals[i][0]
        # Binary search
        left, right = 0, i - 1
        while left <= right:
            mid = (left + right) // 2
            if intervals[mid][1] <= start_i:
                prev[i] = mid
                left = mid + 1
            else:
                right = mid - 1
    
    # DP
    dp = [0] * n
    dp[0] = intervals[0][2]
    
    for i in range(1, n):
        # Don't include interval i
        weight1 = dp[i-1]
        
        # Include interval i
        weight2 = intervals[i][2]
        if prev[i] != -1:
            weight2 += dp[prev[i]]
        
        dp[i] = max(weight1, weight2)
    
    # Reconstruct solution
    selected = []
    i = n - 1
    while i >= 0:
        if prev[i] == -1:
            if intervals[i][2] > 0:
                selected.append(i)
            break
        
        if dp[i] == intervals[i][2] + dp[prev[i]]:
            selected.append(i)
            i = prev[i]
        else:
            i -= 1
    
    return dp[n-1], selected[::-1]