Fastest (but too complicated) C++ solution, need someone to simplify it!


  • 0
    Y

    I cannot find an optimal C++ solution here so far, in my opinion, the optimal solution should have the following properties:

    1. do in-place merge/insert/erase..., use the input intervals as final result instead of creating a new vector<Interval>
    2. use binary search to find the start location for merging intervals

    I think my solution satisfies all those requirements, but the problem is it's too long and not clean enough, I don't think it's easy to finish it in a short interview. So really needs someone to simplify it or make it more efficient if possible.
    BTW, I don't think the given function interface is optimal, it returns a vector<Interval>, which means it will create a new vector<Interval> for return anyway, it should request people to modify intervals in place.

    class Solution {
    public:
        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
            // Given a set of sorted non-overlapping (guaranteed) intervals
            // first deal empty case
            if (intervals.size()==0) {
                intervals.emplace_back(newInterval);
                return intervals;
            }
            
            int idx = binarySearch(intervals, newInterval); // need to handle single-element case
            if (idx==-1) {
                if (newInterval.end < intervals[0].start) { // non-overlapping
                    pureInsert(intervals, newInterval, 0);
                    return intervals;
                } else { // overlapping
                    intervals[0] = Interval(newInterval.start, max(newInterval.end, intervals[0].end));
                    mergeIntervals(intervals, 0);
                    return intervals;
                }
            }
            if (idx==intervals.size()-1) {
                if (intervals[intervals.size()-1].end < newInterval.start) { // non-overlapping
                    intervals.emplace_back(newInterval);
                    return intervals;
                } else { // overlapping
                    intervals[intervals.size()-1].end = max(intervals[intervals.size()-1].end, newInterval.end);
                    return intervals;
                }
            }
            // not boundary cases, valid idx, idx+1
            if (intervals[idx].end < newInterval.start && newInterval.end < intervals[idx+1].start) { // non-overlapping
                pureInsert(intervals, newInterval, idx+1);
                return intervals;
            } else if (intervals[idx].end >= newInterval.start) { // overlapping case#1
                intervals[idx] = Interval(intervals[idx].start, max(intervals[idx].end, newInterval.end));
                mergeIntervals(intervals, idx);
                return intervals;
            } else { // overlapping case#2: intervals[idx].end < newInterval.start, newInterval.end >= intervals[idx+1].start
                intervals[idx+1] = Interval(newInterval.start, max(intervals[idx+1].end, newInterval.end));
                mergeIntervals(intervals, idx+1); // should not touch intervals[idx]
                return intervals;
            }
        }
    private:
        int binarySearch(vector<Interval>& intervals, Interval newInterval) { // last "<=" element
            if (intervals[0].start > newInterval.start) return -1;
            if (intervals[intervals.size()-1].start <= newInterval.start) return intervals.size()-1;
            // the above covered single-ele case, and won't go below
            // now size>=2, guaranteed 2 ends
            int idxL=0, idxH=intervals.size()-1, mid;
            while (1) {
                mid = idxL + (idxH-idxL)/2;
                if (mid == idxL) return idxL; // finally for all cases
                if (intervals[mid].start <= newInterval.start) idxL = mid;
                else idxH = mid;
            }
            // won't reach here
            return -1;
        }
        void pureInsert(vector<Interval>& intervals, Interval newInterval, int idx) {
            intervals.emplace_back(newInterval);
            Interval tmp;
            for (int i=idx; i<intervals.size(); i++) { // it includes final one self-swapping, it's a don't case
                swap(intervals[i], intervals.back(), tmp);
            }
        }
        void mergeIntervals(vector<Interval>& intervals, int idx) { // merge intervals if needed start from idx
            // in-place merge, move forwards in vector, then pop_back
            int curIdx = idx; // current merging idx
            for (int i=idx+1; i<intervals.size(); i++) { // starts are sorted
                if (intervals[curIdx].end >= intervals[i].start) { // merge in
                    intervals[curIdx].end = max(intervals[curIdx].end, intervals[i].end);
                } else { // move forwards
                    intervals[curIdx+1] = intervals[i];
                    curIdx++; // update working idx
                }
            }
            // pop_back until size == curIdx+1 i.e., [0,...,curIdx]
            while (intervals.size() > curIdx+1) intervals.pop_back();
            // test this function alone okay
        }
        template <typename T>
        void swap(T& a, T& b, T& tmp) {
            tmp = a;
            a = b;
            b = tmp;
        }
    };
    
    

Log in to reply
 

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