I need to come up with a linear time algorithm for the following problem:
"You are given an input array containing n intervals whose endpoints are distinct integers between 1 and 10n. Each interval has the form of I(a(i), b(i)) for which holds that 1 <= a(i) <= b(i) <= n. Report all non-containing intervals"
I figured out that for a containing interval it needs to hold that a(j)<=a(i) AND b(j) >= b(i) in wich I(i) is contained in I(j).
The first step that would seem most likely to me was to use Countsort on the endpoints so that we could use the fact that every endpoint of an arbitrary element right in the array will be greater than the element currently visited.
But every solution I try next has resulted in a non-linear running time. I may use additional storage.