There are $n$ intervals on the real line , the intervals are given with start- and end point. The $i$-th interval is $(d_i,f_i)$ where $d_i$ is the start point and $f_i$ is the end point$d_i<f_i$. it is given that $d_i,f_i\in \mathbb Z$ and $0<d_i,f_i<n^4$

Write an algorithm that checks if all intervals are disjoint.

e.g for $n=3\qquad (2,5),(6,7),(1,4)$ the algorithm will return false

because $3$ is common for $(1,4),(2,5)$

For $n=2\qquad (6,7),(1,4)$ the algorithm will return true

I've been stuck for a couple of hours, I thought maybe I could put all pairs of points into an array but I'm not sure if I should sort the array or not. Any hints please on how to approach this question?

  • $\begingroup$ You could write an algorithm that checks for each point $\in \mathbb{Z}$ in each interval if it is present in any other interval. Or would that be too inefficient? $\endgroup$ – Auberon Apr 3 '16 at 19:36
  • $\begingroup$ Is this a homework assignment? $\endgroup$ – jbapple Apr 3 '16 at 20:05
  • 1
    $\begingroup$ I believe meta.cs.stackexchange.com/questions/468/homework-policy is the actual homework policy, including "All users should be aware that askers might use cs.SE to cheat and are asked to act responsibly (e.g. by not answering, answering after a delay or providing only hints) if they suspect a question is a mere restatement of a homework exercise without own effort." $\endgroup$ – jbapple Apr 3 '16 at 21:13
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your homework exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. $\endgroup$ – D.W. Apr 4 '16 at 0:09
  • 1
    $\begingroup$ @Auberon This algorithm runs in time $O(n^5)$. We can do much better. $\endgroup$ – Yuval Filmus Apr 5 '16 at 9:59

You can solve this in $O(n)$. Here are some hints:

  1. Consider a set of disjoint intervals on the line, sorted from left to right, with endpoints $(x_1,y_1),\ldots,(x_n,y_n)$. Then $x_1 < y_1 < x_2 < y_2 < \cdots < x_n < y_n$. Given unsorted disjoint intervals, you can recover this order by looking only at the $x$s or only at the $y$s. Use this idea to solve your problem in $O(n\log n)$.

  2. Since $0 < x_i,y_i < n^4$ in your case, you can use radix sort to improve the running time to $O(n)$. Think of each $x_i$ or $y_i$ as a base $n$ number with 4 digits.

| cite | improve this answer | |

Two intervals, say $i, j$, have some thing in common only if $d_i \leq d_j$ and $d_j \leq f_i$ (or $d_j \leq d_i$ and $d_i \leq f_j$, no difference does it make).

So you can simply sort the intervals by the start point of the intervals. For each interval $i,j$ where $d_i \leq d_j$, you should check if $d_j \leq f_i$ holds. If so then the interval $[d_j,f_i]$ is the shared interval between $i,j$. For $n$ intervals you need $O(n\log n)$ to sort and there are $ \binom {n} {2}$ cases to check the start and end point of intervals, so it takes $O(n^2)$ time complexity. In the aggregate the algorithm takes $O(n^2)$ time.

| cite | improve this answer | |
  • 2
    $\begingroup$ If you're going to use quadratic time, you can just check every pair for intersection, exhaustively - no need to sort. $\endgroup$ – jbapple Apr 3 '16 at 20:41
  • 1
    $\begingroup$ Why do we have to check all pairs after sorting? Won't looking at the next interval suffice? $\endgroup$ – Hendrik Jan Apr 3 '16 at 21:49
  • $\begingroup$ You might consider not encouraging undesirable posting behaviour. Up to you -- your choice. $\endgroup$ – D.W. Apr 4 '16 at 0:09
  • $\begingroup$ A better idea is to sort using radix sort $\endgroup$ – 3SAT Apr 4 '16 at 19:54
  • 1
    $\begingroup$ @Drupalist You might have missed that all numbers are in $(0,n^4)$. $\endgroup$ – Yuval Filmus Apr 5 '16 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.