Overview

This is a problem where you select meeting requests such that no two meetings overlap in time, maximizing the total profit. This is a classic problem known as the Weighted Interval Scheduling problem, which can be solved efficiently by combining dynamic programming (DP) with binary search.

Analysis

Key Observation

Each meeting occupies an interval \([L_i, R_i]\), and overlapping intervals cannot be selected simultaneously. Since the profit \(V_i\) differs for each meeting, we need to “select meetings to maximize the total profit” rather than simply “select as many as possible.”

Naive Approach and Its Issues

A naive approach would be to try all \(2\) choices (approve/reject) for each of the \(N\) requests via brute-force search. However, this would require examining \(O(2^N)\) combinations, which is far too slow for \(N \leq 2 \times 10^5\).

Solution Strategy

Sort the meetings by end time in ascending order, then apply DP.

When meetings are sorted by end time, we can see the structure: “If we select the \(i\)-th meeting, then the only meetings we can select before it are those with end time at most \(L_i - 1\).” The “last meeting ending at or before \(L_i - 1\)” can be found efficiently using binary search on the sorted end times.

Algorithm

1. Sort: Sort the \(N\) meetings in ascending order of end time \(R_i\).

2. DP Definition: Let \(dp[i]\) be “the maximum profit when only considering the first \(i\) meetings after sorting.” The initial value is \(dp[0] = 0\).

3. Transition: For the \(i\)-th meeting (0-indexed), take the larger of the following two options:

   • Do not select the \(i\)-th meeting: \(dp[i+1] = dp[i]\)
   • Select the \(i\)-th meeting: Use binary search to find the latest meeting (index \(j\)) that ends before the start time \(L_i\) of the \(i\)-th meeting, then \(dp[i+1] = dp[j] + V_i\)

That is: $\(dp[i+1] = \max(dp[i],\; dp[j] + V_i)\)\( Here, \)j\( is the number of meetings with end time at most \)L_i - 1\( (= the maximum index in the sorted array satisfying end time \)\leq L_i - 1\(, plus \)1$).

1. Answer: Output \(dp[N]\).

Concrete Example

For example, suppose 3 meetings are given as follows:

Meeting	\(L\)	\(R\)	\(V\)
A	1	3	10
B	2	5	8
C	4	6	12

Sorted by end time: A → B → C.

• \(dp[0] = 0\)
• Meeting A (\(R=3, L=1, V=10\)): No meeting ends at or before \(L-1=0\) (\(j=0\)). \(dp[1] = \max(0, 0+10) = 10\)
• Meeting B (\(R=5, L=2, V=8\)): No meeting ends at or before \(L-1=1\) (\(j=0\)). \(dp[2] = \max(10, 0+8) = 10\)
• Meeting C (\(R=6, L=4, V=12\)): Meeting A ends at or before \(L-1=3\) (\(j=1\)). \(dp[3] = \max(10, 10+12) = 22\)

The answer is \(22\) (selecting meetings A and C).

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for sorting, \(O(\log N)\) for binary search per meeting)
• Space complexity: \(O(N)\) (for storing the meeting list and DP array)

Implementation Notes

• Sorting by end time is a prerequisite for this algorithm. Forgetting to sort will produce incorrect results.

• In the binary search, we look for meetings with “end time at most \(L_i - 1\).” Python’s bisect_right(ends, L_i - 1, 0, i) returns the first position in ends[0:i] that is greater than \(L_i - 1\), so this value directly gives us “the number of meetings satisfying the condition, \(j\)” (= the DP index).

• Managing the \(dp\) array as 1-indexed with \(dp[0] = 0\) (the state where nothing is selected) as the base case makes the transitions straightforward to write.

  Source Code

import sys
from bisect import bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    meetings = []
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        meetings.append((R, L, V))
    
    # Sort by end time
    meetings.sort()
    
    # ends[i] = end time of i-th meeting (0-indexed, sorted)
    ends = [m[0] for m in meetings]
    
    # dp[i] = max profit considering first i meetings (1-indexed)
    # dp[0] = 0
    dp = [0] * (N + 1)
    
    for i in range(N):
        R, L, V = meetings[i]
        # Find the latest meeting that ends before L (i.e., end <= L-1)
        # We need the largest j such that ends[j] <= L-1, j < i
        j = bisect_right(ends, L - 1, 0, i)
        # j is the number of meetings among first i that end <= L-1
        dp[i + 1] = max(dp[i], dp[j] + V)
    
    print(dp[N])

main()

---

This editorial was generated by claude4.6opus-thinking.