Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Well, I was bored last night so I did this in Python. It's recursive unnecessarily (I just read The Little Schemer and think recursion is super neat right now) but it solves your problem and handles all input I threw at it.</p> <pre class="lang-py prettyprint-override"><code>intervals = [(0,4), (5,13), (8,19), (10,12)] def overlaps(x,y): x1, x2 = x y1, y2 = y return ( (x1 &lt;= y1 &lt;= x2) or (x1 &lt;= y2 &lt;= x2) or (y1 &lt;= x1 &lt;= y2) or (y1 &lt;= x2 &lt;= y2) ) def find_overlaps(intervals, checklist=None, pending=None): if not intervals: return [] interval = intervals.pop() if not checklist: return find_overlaps(intervals, [interval], [interval]) check = checklist.pop() if overlaps(interval, check): pending = pending or [] checklist.append(check) checklist.append(interval) return pending + [interval] + find_overlaps(intervals, checklist) else: intervals.append(interval) return find_overlaps(intervals, checklist) </code></pre> <p>Use like this:</p> <pre class="lang-py prettyprint-override"><code>&gt;&gt;&gt; find_overlaps(intervals) [(10, 12), (8, 19), (5, 13)] </code></pre> <p>Note that it returns all overlapping intervals in REVERSE order of their start point. Hopefully that's a minor issue. That's only happening because I'm using <code>push()</code> and <code>pop()</code> on the list, which operates on the end of the list, rather than <code>insert(0)</code> and <code>pop(0)</code> which operates on the beginning. </p> <p>This isn't perfect, but it runs in linear time. Also remember that the size of the actual string doesn't matter at all - the running time is relative to the number of intervals, not the size of the string. </p>
    singulars
    1. This table or related slice is empty.
    1. POEfficient algorithm to find String overlaps
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USTriptych
    1. USTriptych
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POEfficient algorithm to find String overlaps
      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. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYes, I know that the length of the string does not matter. I've also implemented something similar in linear time, but I was hoping I could do something better. I think interval trees can get us down to O(log n), though I haven't read up on them properly yet.
      singulars
      1. PO
      1. USefficiencyIsBliss
 

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