I.cpp

vector<interval_t> pass_lane(vector<interval_t> &gaps, vector<interval_t> &time_intervals)
{
  vector<interval_t> result;

  // assert: gaps are increasing and non-overlapping. 
  // assert: time_intervals are increasing and non-overlapping.

  int idx = 0;
  FOREACH(time_intervals, t) {
    while (idx < gaps.size()) {
      interval_t g = gaps[idx];
      if (g.first > t->second + time_to_pass_a_lane) break;
      interval_t next = intersect(g, make_pair(t->first, t->second + time_to_pass_a_lane));
      next.second -= time_to_pass_a_lane;
      if (non_empty(next)) result.push_back(next);
      idx++;
    }
  }

  return result;
}