证明：
Sort the haybales by location. Consider two haybales i and j such that Bessie can start somewhere between those haybales and break through all the haybales from i+1 to j−1, but she can't break haybale i or haybale j.
It must be the case then that no haybale between i and j is strictly taller than those two.
That motivates the following O(NlogN)solution:
Sort the haybales in decreasing order of size. Consider having an empty road, and place the haybales in that order. When placing a haybale, look immediately to its left and to its right and see if you can break through either one of those haybales if you were inside that interval. Mark that interval as "trapped" if so.
This will be O(NlogN)
as long as you check to make sure that the interval isn't already marked as trapped.
按重量从大到小排序，可以保证区间不会被漏掉