algorithm - 如何处理呢？

最近在我的采访中，有人问我一个算法问题：
给定n行草的高度h[n]。一个农民做了K次以下的操作->
选择开始索引（S）、结束索引（E）和高度（H）。将他的割草器固定在高度h处，并将草从s行修剪到e行。意思是，对于s和e之间的i，h[i]=min（h[i]，h）。
k操作后打印所有高度。
注意->如果H[i]是6，H是4，则在修剪后H[i]变为4（不减少4）
禁止使用segment/fenwick tree，采访想要比o（nk）更好的东西。如何解决这个问题？
这个问题也可以在
http://www.geeksforgeeks.org/directi-interview-set-12-on-campus/
（第4轮问题）

最佳答案

其思想是删除多余的操作，然后只在执行min（h[i]，h）时通过数组，保留所有的高度设置，这将是o（n）。移除冗余操作需要您对它们进行排序和一些FOS，因此复杂性将是O（n+kLoG（k）+k）＝O（n+kLoG（k））。
要删除多余的操作，首先只根据初始位置对它们进行排序。
然后：

for(int x=0;x<oper.length;x++){
    int curr = x+1;
    while(oper[curr].start<oper[x].end){
        if(oper[curr].height > oper[x].height)
            oper[curr].start = oper[x].end;// When you for through the operations you will go from the start to the end of it, if the start is after the end you will not trim
        else { // oper[curr].height<=oper[x].height
            if(oper[x].end<oper[curr].end){
                oper[x].end = oper[curr].start;
            }
            else {
                /**
                 * Make another operation that starts at the end of oper[curr]
                 * and ends at the end of oper[x], and insert it accordingly
                 * in oper. Then make oper[x] end at oper[curr].start
                 * */
            }
        }
        curr++;
    }
}
// Now no operation overlaps with one another.
// When operations where overlapping only the minimum was saved

// Now trim
for(int x = 0;x<oper.length;x++){
    for(int s = oper[x].start;s<oper[x].end;s++){
        h[s] = min(oper[x].height,h[s]);
    }
}

结合多米尼克的方法来节省高度，你有一个非常快速的算法。