基於投影點對時間間隔進行分組的最佳方式

Question

想象一下，我們已經對時間間隔列表進行了排序（按開始時間排序）。 我正在尋找最佳解決方案，將這些間隔「投影」到軸上，從而得到一組對象，描述：投影間隔開始&結束時間和落入預計間隔的源間隔數組。

讓我的例子來說明：假設我們有4個區間爲輸入（按開始時間排序，然後按結束時間）：

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

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

在這種情況下，我希望得到5個元素的數組，每個元素是描述區間開始/結束的對象和源區間的列表。座標軸上的數字顯示該列表中的項目數量。

請幫我找到解決這個任務

Answer 1

最後我找到了最有效的方法。它使用一個排序操作和O（N * 2）迭代來生成結果。

public IEnumerable<DateProjectedItems<T>> Project(IList<T> items) 
{ 
    if (items.Count <= 1) 
    { 
     if (items.Count == 0) 
     { 
      yield break; 
     } 
     yield return new DateProjectedItems<T> 
     { 
      DateRange = items[0].DateRange, 
      Items = items 
     }; 
    } 
    else 
    { 
     var endOrdered = items.OrderBy(i => i.DateRange.DateTimeTo).ToList(); 
     var active = new List<T>(); 
     DateTime? last = null;     
     foreach (var pair in TwoArrayIterator(items, endOrdered)) 
     { 
      DateTime current = pair.Key == 1 ? pair.Value.DateRange.DateTimeFrom : pair.Value.DateRange.DateTimeTo; 
      if (last != null && current != last) 
      { 
       yield return new DateProjectedItems<T> 
       { 
        DateRange = new DateRange(last.Value, current), 
        Items = active.ToList() 
       }; 
      } 
      if (pair.Key == 1) 
      { 
       active.Add(pair.Value); 
      } 
      else 
      { 
       active.Remove(pair.Value); 
      } 
      last = current; 
     }    
    } 
} 

public IEnumerable<KeyValuePair<int, T>> TwoArrayIterator(IList<T> arr1, IList<T> arr2) 
{ 
    var index1 = 0; 
    var index2 = 0; 
    while (index1 < arr1.Count || index2 < arr2.Count) 
    { 
     if (index1 >= arr1.Count) 
      yield return new KeyValuePair<int, T>(2, arr2[index2++]); 
     else if (index2 >= arr2.Count) 
      yield return new KeyValuePair<int, T>(1, arr1[index1++]); 
     else 
     { 
      var elt1 = arr1[index1]; 
      var elt2 = arr2[index2]; 
      if (elt1.DateRange.DateTimeFrom < elt2.DateRange.DateTimeTo) 
      { 
       index1++; 
       yield return new KeyValuePair<int, T>(1, elt1); 
      } 
      else 
      { 
       index2++; 
       yield return new KeyValuePair<int, T>(2, elt2); 
      } 
     } 
    } 
} 

Answer 2

像這樣的事情最快的方法？

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 

實例：

>>> 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++版本與聰明數據結構的使用。

#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('\n'); 
    } 
    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); 
}