C++ Concise O(nlogn) solution Binary Search


  • 0
    Z
    class Solution {
    public:
        static bool mycomp(const Interval &it1, const Interval &it2) {
            return it1.start < it2.start;
        }
        vector<int> findRightInterval(vector<Interval>& intervals) {
            if (intervals.empty()) return {};
            int size = intervals.size();
            vector<int> res(size);
            for (int i = 0; i < size; ++i) {
                res[i] = intervals[i].end;
                intervals[i].end = i;
            }
            sort(intervals.begin(), intervals.end(), &mycomp);
            for (int i = 0; i < size; ++i) {
                int tgt = res[i], begin = 0, end = size - 1;
                res[i] = -1;
                while (begin <= end) {
                    int mid = begin + ((end - begin)>>1);
                    if (intervals[mid].start == tgt) {
                        res[i] = intervals[mid].end;
                        break;
                    } else if (intervals[mid].start > tgt) {
                        res[i] = intervals[mid].end;
                        end = mid - 1;
                    } else begin = mid + 1;
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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