Maximum Profit in Job Scheduling

You are given n jobs, each with a start time, an end time, and a profit. Choose a subset of non-overlapping jobs to maximize total profit. A job that ends at time t does not overlap a job that starts at time t. Print the maximum profit. Input format: - First line: n - Next n lines: start end profit

1 <= n <= 10^5
1 <= start < end <= 10^9
1 <= profit <= 10^9
The answer fits in a signed 64-bit integer.

4
1 3 50
2 4 10
3 5 40
3 6 70

120

5
1 3 20
2 5 20
3 10 100
4 6 70
6 9 60

150