title: Interval tree with added dimension of subset matching?
body: <p>This is an algorithmic question about a somewhat complex problem. The foundation is this:</p>
  
  <p>A scheduling system based on <em>available slots</em> and <em>reserved slots</em>. Slots have certain criteria, let's call them <em>tags</em>. A reservation is matched to an available slot by those tags, if the available slot's tag set is a superset of the reserved slot.</p>
  
  <p>As a concrete example, take this scenario:</p>
  
  <pre><code>11:00  12:00  13:00
  +--------+
  | A, B   |
  +--------+
         +--------+
         | C, D   |
         +--------+
  </code></pre>
  
  <p>Between the times of 11:00 to 12:30 reservations for the tags <code>A</code> and <code>B</code> can be made, from 12:00 to 13:30 <code>C</code> and <code>D</code> is available, and there's an overlap from about 12:00 to 12:30.</p>
  
  <pre><code>11:00  12:00  13:00
  +--------+
  | A, B   |
  +--------+
         +--------+
         | C, D   |
         +--------+
    xxxxxx
    x A  x
    xxxxxx
  </code></pre>
  
  <p>Here a reservation for <code>A</code> has been made, so no other reservations for <code>A</code> or <code>B</code> can be made between 11:15-ish and 12:00-ish.</p>
  
  <p>That's the idea in a nutshell. There are no specific limitations for the available slots:</p>
  
  <ul>
  <li>an available slot can contain any number of tags</li>
  <li>any number of slots can overlap at any time</li>
  <li>slots are of arbitrary length</li>
  <li>reservations can contain any number of tags</li>
  </ul>
  
  <p>The only rule that needs to be obeyed in the system is:</p>
  
  <ul>
  <li>when adding a reservation, at least one remaining available slot must match all the tags in the reservation</li>
  </ul>
  
  <p>To clarify: when there are two available slots at the same time with, say, tag <code>A</code>, then two reservations for <code>A</code> can be made at that time, but no more.</p>
  
  <p>I have that working with a modified implementation of an <a href="https://en.wikipedia.org/wiki/Interval_tree" rel="noreferrer">interval tree</a>; as a quick overview:</p>
  
  <ul>
  <li>all available slots are added to the interval tree (duplicates/overlaps are preserved)</li>
  <li>all reserved slots are iterated and:
  
  <ul>
  <li>all available slots matching the time of the reservation are queried from the tree</li>
  <li>the first of those matching the reservation's tags is sliced and the slice removed from the tree</li>
  </ul></li>
  </ul>
  
  <p>When that process is finished, what's left are the remaining slices of available slots, and I can query whether a new reservation can be made for a particular time and add it.</p>
  
  <p>Data structures look something like this:</p>
  
  <pre><code>{
    type: 'available', 
    begin: 1497857244, 
    end: 1497858244, 
    tags: [{ foo: 'bar' }, { baz: 42 }]
  }
  {
    type: 'reserved', 
    begin: 1497857345, 
    end: 1497857210, 
    tags: [{ foo: 'bar' }]
  }
  </code></pre>
  
  <p>Tags are themselves key-value objects, a list of them is a "tag set". Those could be serialised if it helps; so far I'm using a Python <code>set</code> type which makes comparison easy enough. Slot begin/end times are UNIX time stamps within the tree. I'm not particularly married to these specific data structures and can refactor them if it's useful.</p>
  
  <hr>
  
  <p>The problem I'm facing is that this doesn't work bug-free; every once in a while a reservation sneaks its way into the system that conflicts with other reservations, and I couldn't yet figure out how that can happen exactly. It's also not very clever when tags overlap in a complex way where the optimal distribution needs to be calculated so all reservations can be fit into     the available slots as best as possible; in fact currently it's non-deterministic how reservations are matched to available slots in overlapping scenarios.</p>
  
  <p>What I want to know is: interval trees are mostly great for this purpose, but my current system to add tag set matching as an additional dimension to this is clunky and bolted-on; <strong>is there a data structure or algorithm that can handle this in an elegant way?</strong></p>
  
  <p>Actions that must be supported:</p>
  
  <ol>
  <li>Querying the system for available slots that match certain tag sets (taking into account reservations that may reduce availability but are not themselves part of said tag set; e.g. in the example above querying for an availability for <code>B</code>).</li>
  <li>Ensuring no reservations can be added to the system which don't have a matching available slot.</li>
  </ol>