Savvy Seller

면접 대비

시간 제한1초메모리 제한1024 MB

요약

시작 시간, 끝 시간, 이익이 주어진 N개의 회의 중에서 서로 겹치지 않는 부분집합을 골라 총이익을 최대로 만든다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

Hanbyeol is a seasoned sales representative. She has $N$ meeting opportunities with various companies and wants to select some of these meetings to attend. In her early career as a junior saleswoman, she aimed to attend as many meetings as possible. However, now, as a veteran, she knows which meetings are more important and which are less critical.

Hanbyeol knows the start and end times for each meeting and the expected profit she can earn by attending. If two meetings overlap in time, she cannot attend both. It is implied that meetings are considered overlapping only if one meeting's end time exceeds the next meeting's start time; meetings, where the end time of one equals the start time of the next, are allowed.

Write a program to help Hanbyeol create a meeting schedule that maximizes her total expected profit.

입력

The first line contains a single integer, $N$ , denoting the meeting opportunities that Hanbyeol has. ( $1 \le N \le 100\\,000$ )

The $i$ -th of the next $N$ lines contain three space-separated integers: $s\_i$ and $e\_i$ , denoting the starting and ending time of the $i$ -th meeting, respectively, and $p\_i$ , denoting the expected profit Hanbyeol can earn by attending the $i$ -th meeting. ( $0 \le s < e \le 10^9;$ $1 \le p \le 10^9$ )

출력

Output the total profit when Hanbyeol schedules her meetings optimally.

예제2

예제 1
입력
```
4
1 5 1
2 4 1
6 8 1
5 12 1
```
예상 출력
```
2
```
예제 2
입력
```
4
1 5 7
2 7 16
6 8 18
7 12 6
```
예상 출력
```
25
```