patternMinor
Finding nested intervals efficiently
Viewed 0 times
nestedintervalsefficientlyfinding
Problem
The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique.
If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$
How do I find out which intervals are nested in others efficiently?
The hint is to use two induction hypotheses: one to assume you can solve the problem for $n-1$ intervals, another that you can find the largest right endpoint for the $n-1$ intervals.
How do I use this information to do the inductive step in constant time?
If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$
How do I find out which intervals are nested in others efficiently?
The hint is to use two induction hypotheses: one to assume you can solve the problem for $n-1$ intervals, another that you can find the largest right endpoint for the $n-1$ intervals.
How do I use this information to do the inductive step in constant time?
Solution
This problem is as hard as comparison sorting, given
You can make interval set from input number set $S$ (w.l.o.g suppose input numbers are in $Z^+$) as follow:
$ \Gamma = \{(a,b) \mid a\in S \wedge b=\max_{t\in S} \{2\cdot t - a + 1 \} \}$
Above transformation can be done in $O(n)$.
But if you find a nesting relation in this interval set in $o(n \log n)$, you can sort input array in $o(n \log n)$, But comparison sorting barrier is $\Omega(n \log n)$, So the algorithm which finds interval nesting cannot be better than $\Omega(n \log n)$ with respect to comparision sorting barrier, But also $O(n \log n)$ algorithm is trivial.
n input number sort them.You can make interval set from input number set $S$ (w.l.o.g suppose input numbers are in $Z^+$) as follow:
$ \Gamma = \{(a,b) \mid a\in S \wedge b=\max_{t\in S} \{2\cdot t - a + 1 \} \}$
Above transformation can be done in $O(n)$.
But if you find a nesting relation in this interval set in $o(n \log n)$, you can sort input array in $o(n \log n)$, But comparison sorting barrier is $\Omega(n \log n)$, So the algorithm which finds interval nesting cannot be better than $\Omega(n \log n)$ with respect to comparision sorting barrier, But also $O(n \log n)$ algorithm is trivial.
Context
StackExchange Computer Science Q#7073, answer score: 4
Revisions (0)
No revisions yet.