algorithm - Optimal way to group time intervals based on projected points

Question

Imagine we have sorted list of time intervals (sorted by time of beginning). I'm looking for optimal solution to 'project' these intervals to axis, having as a result an array of objects, describing: projected interval start&end time and arrays of source intervals that fall into projected intevals.

Let me explain on example: imagine we have 4 intervals as input (sorted by start time, then by end time):

   [---R1---)    
         [-----R2-----)
         [---------R3-------)
                 [----R4----)

 --|-----|--|----|----|-----|---> t (time axis)
      1    3   2    3    2 

In that case I'm expecting to get array of 5 elements, each element is an object describing interval start/end and a list of source intervals. Numbers under axis on chart shows number of items in that list.

Please, help me to find fastest way to solve this task

Answer 1

Something like this?

def groupIntervals(intervals):
    events = {}
    for start, stop, name in intervals:
        if start not in events: events[start] = []
        events[start].append(('start', name))
        if stop not in events: events[stop] = []
        events[stop].append(('stop', name))
    last = None
    output = []
    active = set()
    for time in sorted(events.keys()):
        if active and last is not None:
            output.append((last, time, active.copy()))
        last = time
        for action, name in events[time]:
            if action == 'start': active.add(name)
            elif action == 'stop': active.remove(name)
            else: assert False
    return output

Example usage:

>>> groupIntervals([(1, 3, 'R1'), (2, 5, 'R2'), (2, 6, 'R3'),
...                 (4, 6, 'R4')])
[(1, 2, set(['R1'])),
 (2, 3, set(['R1', 'R2', 'R3'])),
 (3, 4, set(['R2', 'R3'])),
 (4, 5, set(['R4', 'R2', 'R3'])),
 (5, 6, set(['R4', 'R3']))]

C++ version with cleverer data structure usage.

#include <cstdio>
#include <limits>
#include <list>
#include <queue>
#include <string>
#include <vector>

struct Interval {
  Interval(std::string name, int start, int stop);
  std::string name;
  int start;
  int stop;
};

Interval::Interval(std::string name, int start, int stop)
    : name(name), start(start), stop(stop) {
}

typedef std::list<std::vector<Interval>::const_iterator> ActiveList;

struct StopEvent {
  StopEvent(int stop, ActiveList::iterator j);
  int stop;
  ActiveList::iterator j;
};

StopEvent::StopEvent(int stop, ActiveList::iterator j)
    : stop(stop), j(j) {
}

struct StopEventGreater {
  bool operator()(StopEvent const& a,
                  StopEvent const& b) const;
};

bool StopEventGreater::operator()(StopEvent const& a,
                                  StopEvent const& b) const {
  return a.stop > b.stop;
}

void Sweep(std::vector<Interval> const& intervals) {
  std::vector<Interval>::const_iterator i(intervals.begin());
  std::priority_queue<StopEvent,
      std::vector<StopEvent>,
      StopEventGreater> active_queue;
  ActiveList active_list;
  int last_time(std::numeric_limits<int>::min());
  while (i != intervals.end() || !active_queue.empty()) {
    bool start(i != intervals.end() &&
               (active_queue.empty() || i->start < active_queue.top().stop));
    int time(start ? i->start : active_queue.top().stop);
    if (time != last_time && !active_list.empty()) {
      std::printf("[%d, %d):", last_time, time);
      for (ActiveList::const_iterator j(active_list.begin());
           j != active_list.end();
           ++j) {
        std::printf(" %s", (*j)->name.c_str());
      }
      std::putchar('
');
    }
    last_time = time;
    if (start) {
      active_queue.push(StopEvent(i->stop,
                                  active_list.insert(active_list.end(), i)));
      ++i;
    } else {
      active_list.erase(active_queue.top().j);
      active_queue.pop();
    }
  }
}

int main(void) {
  std::vector<Interval> intervals;
  intervals.push_back(Interval("R1", 0, 4));
  intervals.push_back(Interval("R2", 1, 9));
  intervals.push_back(Interval("R3", 1, 11));
  intervals.push_back(Interval("R4", 6, 11));
  Sweep(intervals);
}