Simple boundary check version


  • 0
    Y

    boundary check may be simpler if you choose proper first and last overlapping index.
    Is there any better solution? I will appreciate it!

    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
    int l = 0, r = intervals.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (newInterval.start == intervals[mid].end) { l = mid; break; }
        else if (newInterval.start > intervals[mid].end) { l = mid + 1; }
        else { r = mid - 1; }
    }
    int start = l;
    r = intervals.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (newInterval.end == intervals[mid].start) { r = mid; break; }
        else if (newInterval.end > intervals[mid].start) { l = mid + 1; }
        else { r = mid - 1; }
    }
    int end = r;
    if (start < intervals.size()) {
        newInterval.start = min(newInterval.start, intervals[start].start);
    }
    if (end >= 0) {
        newInterval.end = max(newInterval.end, intervals[end].end);
    }
    intervals.erase(intervals.begin() + start, intervals.begin() + end + 1);
    intervals.insert(intervals.begin() + start, newInterval);
    return intervals;
    

    }


  • 12
    X

    I use boundary check,and the code is much more neat.

    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ret;
    	int i,n=intervals.size();
    	Interval mergeInterval = newInterval;
    	for(i=0;i<n;i++){
    		if(newInterval.start>intervals[i].end)
    			ret.push_back(intervals[i]);
    		else if(newInterval.end<intervals[i].start)
    			break;
    		else
    			mergeInterval = Interval(min(mergeInterval.start,intervals[i].start)
    			,max(mergeInterval.end,intervals[i].end));
    	}
    	ret.push_back(mergeInterval);
    	for(;i<n;i++)
    		ret.push_back(intervals[i]);
    	return ret;
    }

  • 0
    E

    Your solution is indeed very neat. The logic is very clear and very robust. Should deserve more votes!


  • 1
    W

    Similar thoughts in Java. It check the boundary and keep updating the new interval if there is a merge happens. Otherwise just add it directly without merge. Pretty straightforward.

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<Interval>();
        boolean isAdded = false;
        for(Interval ele: intervals)
        {
            if(ele.start>newInterval.end)
            {
                if(!isAdded){
                    isAdded =true;
                    res.add(newInterval);
                }
                res.add(ele);
            }
            else if(ele.end < newInterval.start)
            {
                res.add(ele);
            }
            else
            {
                newInterval = mergeInterval(ele, newInterval);
            }
        }
        if(!isAdded)
        {
            res.add(newInterval);
        }
        return res;
    }
    
    public Interval mergeInterval(Interval a, Interval b)
    {
        int s = a.start>b.start? b.start:a.start;
        int e = a.end > b.end? a.end:b.end;
        return new Interval(s,e);
    }
    

  • 0
    J

    like the code


Log in to reply
 

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