4-line C++ O(NlogN) solution directly using std::map::lower_bound for right interval start

  • 0

    Note that the problem guarantees different intervals must have different strat points.
    The algorithm is very straightforward:

    1. Build a (sorted) map s2i mapping start point -> index (O(NlogN) time).
    2. For each interval i, its right interval index is simply map::lower_bound(i.end)->second (O(log N) time each).
        vector<int> findRightInterval(vector<Interval>& its) {
          map<int,int> s2i; vector<int> res(its.size(), -1); map<int,int>::iterator j;
          for (int i = 0; i < its.size(); ++i) s2i[its[i].start] = i;
          for (int i = 0; i < its.size(); ++i) if ((j=s2i.lower_bound(its[i].end)) != s2i.end()) res[i] = j->second;
          return res;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.