Databases
StackOverflow2013
Postsdbo
POalgorithm to find longest non-overlapping sequences
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POalgorithm to find longest non-overlapping sequences
    primarykey
    data
    text
    <p>I am trying to find the best way to solve the following problem. By best way I mean less complex.</p> <p>As an input a list of tuples (start,length) such:</p> <pre><code>[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)] </code></pre> <p>Each element represets a sequence by its <em>start</em> and <em>length</em>, for example (5,7) is equivalent to the sequence <code>(5,6,7,8,9,10,11)</code> - a list of 7 elements starting with 5. One can assume that the tuples are sorted by the <code>start</code> element.</p> <p>The output should return a non-overlapping combination of tuples that represent the longest continuous sequences(s). This means that, a solution is a subset of ranges with no overlaps and no gaps and is the longest possible - there could be more than one though. </p> <p>For example for the given input the solution is:</p> <p><code>[(0,5),(5,7)]</code> equivalent to <code>(0,1,2,3,4,5,6,7,8,9,10,11)</code></p> <p>is it backtracking the best approach to solve this problem ?</p> <p>I'm interested in any different approaches that people could suggest.</p> <p>Also if anyone knows a formal reference of this problem or another one that is similar I'd like to get references.</p> <p>BTW - this is not homework.</p> <p><strong>Edit</strong></p> <p>Just to avoid some mistakes this is another example of expected behaviour</p> <p>for an input like <code>[(0,1),(1,7),(3,20),(8,5)]</code> the right answer is <code>[(3,20)]</code> equivalent to (3,4,5,..,22) with length 20. Some of the answers received would give <code>[(0,1),(1,7),(8,5)]</code> equivalent to (0,1,2,...,11,12) as right answer. But this last answer is not correct because is shorter than <code>[(3,20)]</code>.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USDan Nissenbaum
    1. USManuel Salvadores
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POalgorithm to find longest non-overlapping sequences
      1. USManuel Salvadores
      1. VTFavorite
    2. VO
      singulars
      1. POalgorithm to find longest non-overlapping sequences
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POalgorithm to find longest non-overlapping sequences
      1. USvcsjones
      1. VTFavorite
    1. COWhat exactly do you mean by longest continuous lines? Is a single line of length 7 better than two separated ones of length 5 each (e.g. [(0,5), (7,5)] )?
      singulars
      1. POalgorithm to find longest non-overlapping sequences
      1. USRafał Dowgird
    2. COBy longest I mean that for instance [(0,100)] is longer than [(0,10),(10,5)]. Since the first one covers the sequence (0,1,2,...,99) and the second one just (0,1,..,9,10,..,14).
      singulars
      1. POalgorithm to find longest non-overlapping sequences
      1. USManuel Salvadores
    3. CO@msalvadores: So you don't mean "continuous" at all, right? Just the total number of numbers represented? In that case I suggest removing the word "continuous" from your question and rewording slightly.
      singulars
      1. POalgorithm to find longest non-overlapping sequences
      1. USj_random_hacker
 

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