Maximum Interaction Value

Given a set of notifications, each described by a start time, an end time, and an interaction value, your task is to select a compatible subset of notifications such that the sum of their interaction values is maximized. Two notifications are compatible if the end time of one is less than or equal to the start time of the other, i.e. if \(e_i \leq s_j\). This problem can be solved using dynamic programming combined with binary search for efficiency.

Note: The notifications should be processed by sorting them on their end times. For each notification \(i\), you can use binary search to find the rightmost notification \(j\) (where \(j < i\)) such that \(e_j \leq s_i\). The recurrence relation is then:

[ \text{dp}[i] = \max(\text{notifications}[i].v + \text{dp}[j],; \text{dp}[i-1]) ]

where \(\text{dp}[i]\) represents the maximum interaction value using notifications up to the \(i^{th}\) notification.

inputFormat

The first line contains an integer \(n\) representing the number of notifications. Each of the next \(n\) lines contains three integers \(s\), \(e\), and \(v\) separated by spaces, where:

• \(s\) is the start time,
• \(e\) is the end time, and
• \(v\) is the interaction value of the notification.

The input is provided via standard input (stdin).

outputFormat

Output a single integer which is the maximum sum of interaction values that can be achieved by selecting a compatible set of notifications. The output should be written to standard output (stdout).

5
1 3 10
2 5 15
4 6 10
5 8 5
7 9 10

30