两个不相交的间隔最小总和

Question

给定N个区间[a，b]成本c的列表，找到2个非重叠区间的最小总和。我在O（n ^ 2）（pastebin.com/kveAZTwv）中有一个算法，但我找不到O（N log N）。

第一个值是间隔数。其他行是：a，b，c其中a是间隔的开头，b是结束，c是成本。

例如：

input :
3
0 10 1
1 2 2
9 12 2



output :
4

Answer 1

这是O（n log n）中算法的基本思想，我相信它可以更有效地完成：

1）根据其端点对所有间隔进行排序，每个端点是一个潜在的分裂点，其中右边的间隔和左边的间隔不重叠

2）现在扫描已排序的间隔，并为每个spiltpoint记住左边的最小成本间隔。

3）根据起始点对所有元素进行排序

4）对于每个分裂点，另外记住右边的最小成本间隔（在分裂点之后具有其起始点）。通过从排序元素的后面到前面的单次扫描，这也是可能的

5）为每个分裂点添加两个相应的成本并寻找最小值。

对不起，这是一个非正式的，因为我在移动。