You are given a 2D integer array ranges whose length is n where ranges[i]=[start_{i}, end,coins_{i}] means all integers from start_{i} to end_{i} inclusive start_{i} and end_{i} are present and we get coins_{i} amount of coins when we select this i^{th} range. You can select at most two intervals so as to collect maximum coins but if you select two ranges then those two ranges should not intersect or overlap but can touch each other.
Note:
1. You can select at max 2 ranges and they should not intersect with each other but they can touch themselves.
2. Two ranges (A1,A2) and (A3,A4) are overlapping when A3<A2, for example (2,3) and (2,4) are overlapping, (2,5) and (4,6) are overlapping, but (2,3) and (3,4) are not overlapping also (2,2) and (2,2) are not overlapping.
Example 1:
Input :
n=3
ranges={{1,3,4},{2,3,5},{3,4,2}}
Output: 7
Explanation:
We can see that we can take 2nd and
3rd ranges as they are not intersecting
(only touching) we get maximum Coins by
taking these ranges(5+2=7).
Example 2:
Input :
n=5
ranges={{1,3,4},{2,3,5},{3,4,2},{5,8,9},{2,8,10}}
Output: 14
Explanation:
We can see that we can take 2nd and
4th ranges as they are not intersecting
we get maximum Coins(5+9=14) by taking
these ranges.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxCoins() which takes an integer n(length of ranges), integer 2D integer array ranges, and you have to return the maximum number of coins you got after selecting at most two ranges that are not intersecting.
Expected Time Complexity: O(nlogn)
Expected Space Complexity: O(n)
Constraints:
1<=n<=10^{5}
0<=ranges[i][0]<=ranges[i][1]<=10^{9}
0<=ranges[i]2<=10^{6}
The sum of n over all test cases won't exceed 10^{6}

见题面

见题面