Overview

This is a problem of finding the maximum total profit when selecting meeting room reservation requests such that their time slots do not overlap.

Analysis

This problem is a type of weighted interval scheduling problem. Each request has a time interval \([L_i, R_i]\) and a profit \(V_i\), and we need to select a set of non-overlapping intervals to maximize the total profit.

A naive approach would be to sort the intervals by end time and then use dynamic programming to compute the “maximum profit when selecting this interval” for each interval. However, a straightforward implementation would have \(O(N)\) states with \(O(N)\) computation per state, resulting in \(O(N^2)\) overall, which is too slow for the constraint \(N \leq 2 \times 10^5\).

To solve this problem efficiently, we need to speed up the dynamic programming updates. Specifically, processing intervals in increasing order of end time and efficiently updating the DP array is an effective approach.

Algorithm

1. Sort the requests in ascending order of end time \(R_i\), then by ascending order of start time \(L_i\)
2. Prepare a DP array dp[r] (dp[r] = maximum profit when processed up to time slot \(r\))
3. Process time slots \(r\) from \(1\) to \(T\) in order:
   • Initialize dp[r] with dp[r-1] (the choice of not using this time slot)
   • For all requests with end time equal to \(r\):
     • If request \(i\) has start time \(L_i\), then dp[L_i-1] + V_i is the profit when adopting this request
     • Update dp[r] with this value if it improves the current value
4. The final answer is dp[T], which gives the maximum profit

In this approach, by processing intervals in order of end time, the DP updates can be performed efficiently. Each request is processed in constant time, and the overall time complexity is \(O(N \log N + T)\).

Complexity

• Time complexity: \(O(N \log N + T)\)
  • \(O(N \log N)\) for sorting
  • \(O(N + T)\) for the DP computation
• Space complexity: \(O(N + T)\)
  • \(O(N)\) for storing the event list
  • \(O(T)\) for storing the DP array

Implementation Notes

• Efficiently read and parse the input data

• Sort the intervals by end time, then by start time

• Set the DP array size to \(T+2\) to handle boundary conditions (e.g., when \(L_i=0\))

• To process multiple requests with the same end time together, proper sort order and pointer management are important

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
    
    n = int(data[0])
    T = int(data[1])
    index = 2
    events = []
    for i in range(n):
        L = int(data[index]); R = int(data[index+1]); V = int(data[index+2])
        index += 3
        events.append((L, R, V))
    
    events.sort(key=lambda x: (x[1], x[0]))
    
    dp = [0] * (T+2)
    j = 0
    for r in range(1, T+1):
        dp[r] = max(dp[r], dp[r-1])
        while j < n and events[j][1] == r:
            L, R, V = events[j]
            if L > 0:
                candidate = dp[L-1] + V
            else:
                candidate = V
            if candidate > dp[r]:
                dp[r] = candidate
            j += 1
            
    print(dp[T])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.