N intervals are given in format of {start, end, cost} and i have to find out two non-overlapping intervals such that (Interval_1.end- Interval_1.start) +(Interval_2.end- Interval_2.start) is maximum and cost is minimum.
ex:-
for n=5
4 6 5
1 4 10
6 9 4
3 8 6
1 4 5
so, answer is {1,4},{6,9} as this is maximum and minimum cost for maximum range is 5+4=9
First sort all line segments (l,r)
Now check for every segments from there we can choose the next non overlapping segment corresponding to current segment.
For i th segment we get the range L to n.
using segment tree we can figure out maximum
width of the segment let say it W.
Now it is possible that from L to n there are several segments of width W and we have to choose minimum of them.
Last thing we have to do is create segment tree for each width W and query upon it.
As there may possible large range of l,r so we can compress the width W and then create segment trees.
Hope this will help. 