title: Merge two lists of intervals with priority for one list
body: <p>I'm currently stuck with an algorithm problem in which I want to optimize the complexity.</p>
  
  <p>I have two lists of intervals <code>S = [[s1, s2], [s3, s4], ..., [sn-1, sn]]</code> and <code>W = [[w1, w2], [w3, w4], ..., [wm-1, wm]]</code> that I want to merge respecting ordinal order, and <strong>intervals of S have priority over those of W</strong>. (S for strong, W for weak)
  For example, that priority imply :</p>
  
  <ul>
  <li><code>S = [[5,8]]</code> and <code>W = [[1, 5], [7, 10]]</code> will give : <code>res = [[1, 4, W], [5, 8, S], [9, 10, W]]</code>. Here intervals from W are cropped in priority for intervals of S</li>
  <li><code>S = [[5, 8]]</code> and <code>W = [[2, 10]]</code> will give : <code>res = [[2, 4, W], [5, 8, S], [9, 10, W]]</code>. Here the interval of W is split into two parts because S has priority.</li>
  </ul>
  
  <p>While merging those lists, I need to keep track of the strong of weak nature of those intervals by writing a third element beside each interval, that we can call the symbol. that's why the result is something like : [[1, 4, W], [5, 8, S], [9, 10, W]].
  Finally, as the union of all interval does not cover all integers in a certain range, we have a third symbol, let's say B for blank which fill missing interval : <code>[[1, 2, W], [5, 8, S], [9, 10, W], [16, 20, S]]</code> will be filled in to become : <code>[1, 2, W], [3, 4, B], [5, 8, S], [9, 10, W], [11, 15, B], [16, 20, S]]</code></p>
  
  <p>My first attempt was very naive and lazy (because I first wanted it to work) :
  If the greatest integer covered by these two lists of intervals is M, then I created a list of size M filled with B symbols : <code>res = [B]*M = [B, B, B ..., B]</code>
  Then I first take interval from W one by one and rewrite elements from res of index in this interval to change its symbol to W. Next, I do the same with intervals of S, and the priority is respected because I overwrite with the symbol S in the last step.
  It gives something like :</p>
  
  <ol>
  <li><code>[B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B, B]</code></li>
  <li><code>[B, B, B, W, W, W, W, B, W, W, W, W, B, W, W, B, B]</code></li>
  <li><code>[B, B, S, S, W, W, W, B, S, S, W, W, B, S, W, B, B]</code></li>
  </ol>
  
  <p>Finally, I go through the big list one last time to factorize and recreate intervals with its corresponding symbols. Previous example gives :
  <code>[[1, 2, B], [3, 4, S], [5, 7, W], [8, 8, B], [9, 10, S], [11, 12, W], [13, 13, B], [14, 14, S], [15, 15, W], [16, 17, B]]</code></p>
  
  <p>Unfortunately but predictably, this algorithm is not usable in practice : M is around 1000000 in my application and this algorithm is <em>O</em>(n<sup>2</sup>) if I'm not mistaken.</p>
  
  <p><strong>So, I would like some advice and directions to solve this algorithmic complexity problem. I'm sure that this problem looks alike a well-known algorithmic problem but I don't know where to go.</strong></p>
  
  <p>My few ideas to improve that for now can be used to optimize the algorithm, but are quite complex to implement so I think there is better ideas. but here they are :</p>
  
  <ul>
  <li>Do the same kind of overwrite process to respect priority : in list W, insert intervals of S with overwriting when necessary to respect priority. Then fill in this list to insert missing interval with B symbol. But we would have an heavy use of <em>if</em> to compare intervals because of the great amount of cases.</li>
  <li>Construct a new list while browsing S and W step by step. In this idea we would have one cursor by list to go from interval to interval until the end of one of the two lists. Again we use a lot of <em>if</em> and cases we insert intervals in the new list with respect to priority. But it raises the same complex problem with the great amount of cases.</li>
  </ul>
  
  <p>I hope I made myself clear, if not I can explain in other way.
  Please teach me with experience and cleverness :)</p>
  
  <p>Thanks</p>
  
  <p>EDIT: here is my "naive" algorithm code:</p>
  
  <pre><code>def f(W, S, size):
  
    #We first write one symbol per sample
    int_result = ['B'] * size
    for interval in W:
        for i in range(interval[0], interval[1]+1):
            int_result[i] = 'W'
    for interval in S:
        for i in range(interval[0], interval[1]+1):
            int_result[i] = 'S'
  
    #we then factorize: we store one symbol for an interval of the same    symbol.    
    symbols_intervals = []
    sym = int_result[0]
    start = 0
    for j in range(len(int_result)):
        if int_result[j] != sym:
            symbols_intervals.append([start, j-1, sym])
            sym = all_symbols[j]
            start = j
        if j == len(int_result)-1:
            symbols_intervals.append([start, j-1, sym])
  
    return symbols_intervals
  </code></pre>