2 added 225 characters in body
source | link

There are two things to do:

For each start pointer find the maximal end pointer. Note that end is increasing so it's just O(n) iterations.

At each iteration, maintain the minimum and maximum value. This can be done with heaps and sets (or hash maps). The amortized complexity is O(log(k)). You may have O(log n) if you don't use hash maps.

The final complexity is thus O(n log n), and if you allow the hash maps to be O(1), O(n log k).  

@xskxzr proposes an alternative way to compute the range minima and maxima, so the problem is indeed O(n). However I think the algorithm is quite complicated with Cartesian trees so O(n log k) seems to be a simpler solution.

There are two things to do:

For each start pointer find the maximal end pointer. Note that end is increasing so it's just O(n) iterations.

At each iteration, maintain the minimum and maximum value. This can be done with heaps and sets (or hash maps). The amortized complexity is O(log(k)). You may have O(log n) if you don't use hash maps.

The final complexity is thus O(n log n), and if you allow the hash maps to be O(1), O(n log k).  

There are two things to do:

For each start pointer find the maximal end pointer. Note that end is increasing so it's just O(n) iterations.

At each iteration, maintain the minimum and maximum value. This can be done with heaps and sets (or hash maps). The amortized complexity is O(log(k)). You may have O(log n) if you don't use hash maps.

The final complexity is thus O(n log n), and if you allow the hash maps to be O(1), O(n log k).

@xskxzr proposes an alternative way to compute the range minima and maxima, so the problem is indeed O(n). However I think the algorithm is quite complicated with Cartesian trees so O(n log k) seems to be a simpler solution.

1
source | link

There are two things to do:

For each start pointer find the maximal end pointer. Note that end is increasing so it's just O(n) iterations.

At each iteration, maintain the minimum and maximum value. This can be done with heaps and sets (or hash maps). The amortized complexity is O(log(k)). You may have O(log n) if you don't use hash maps.

The final complexity is thus O(n log n), and if you allow the hash maps to be O(1), O(n log k).