Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>For each pair of ranges, build an adjacency matrix (i->j) which means i is a subset of j. You will end up with multiple directed graphs (some of them disconnected from each other).</p> <p>The adjacency matrix can be built as follows: </p> <p>First sort all the start times and end times in ascending order.<br> Then traverse this from left to right and keep a <strong>deque (double ended queue)</strong> of active interval start times in sorted order.<br> Whenever a start point is reached, push_back the interval in the deque.<br> Whenever an end point is reached, it becomes the sub-interval of all intervals in the list whose start times are less than that interval. Pop this interval out from the <strong>front. This shall ensure a time complexity of O(number of super-sets of the interval)</strong><br> Complexity of this operation shall be O(n+E) where n is the number of intervals and E is the number of edges.</p> <p>For each graph, the problem now is finding the longest path in an acyclic directed graph. This <a href="http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/" rel="nofollow">link</a> explains how to solve this problem, with a minor variation that in your problem the costs are associated with nodes rather than edges.</p> <p>EDIT: for the example intervals: </p> <pre><code>1a to 1b | distance 10 1c to 2a | distance 9 2b to 3a | distance 8 3b to 4 | distance 2 </code></pre> <p>The sorted list of start and end times: </p> <pre><code>1a, 1c, 1b, 2b, 2a, 3b, 3a, 4 </code></pre> <p>Whenever the start and end times coincide, we take the start time before the end time. </p> <pre><code>The deque is empty initially. 1a added to deque from the back (start time of 1st interval). 1c added to deque (start time of 2nd interval) The deque is now ___1a1c____ (double ended) 1b (end time of 1st interval encountered) </code></pre> <p>Now pop from the front till you get its start time (1a). </p> <pre><code>____1c_____ </code></pre> <p>Now we see that 1c is equal to 1a, hence we know that the interval whose end time is reached is a subinterval of the interval of 1c. So we build an edge from interval 1 to interval 2.</p> <p>Next 2b is added to deque (start time of 3rd interval)</p> <pre><code>_____1c2b___ </code></pre> <p>2a is then encountered (end time of 2nd interval) </p> <pre><code>_____2b____ </code></pre> <p>Now we see that unlike the 1st pop, here 1c is not equal to 2b, hence there is no subinterval relationship.</p> <p>Next 3b is added to deque (start time of 4th interval)</p> <pre><code>_____2b3b___ </code></pre> <p>3a is then encountered (end time of 3rd interval) </p> <pre><code>_____3b____ </code></pre> <p>Here again we see that, 2b is not equal to 3b, hence there is no subinterval relationship.</p> <p>Similarly for the last interval.</p> <p>So we see that we only end up with 1 edge in the graph and rest all are just one node graphs without any edges.</p> <pre><code>Graph 1 cost: 10 + 9 = 19. Graph 2 cost: 8. Graph 3 cost: 2 </code></pre> <p>.</p>
    singulars
    1. This table or related slice is empty.
    1. POSuperset of Ranges -- Finding greatest distance
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAbhishek Bansal
    1. USAbhishek Bansal
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POSuperset of Ranges -- Finding greatest distance
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. CODoesn't building the matrix take O(n^2) time?
      singulars
      1. PO
      1. US1110101001
    2. CO@user2612743 See my updated answer.
      singulars
      1. PO
      1. USAbhishek Bansal
    3. COI don't quite understand how you build the adjacency matrix. Could you give an example using the ranges given in the original post?
      singulars
      1. PO
      1. US1110101001
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload