[leetcode solution/57]Insert Interval

Datetime:2017-04-01 05:40:01         Topic: LeetCode          Share        Original >>
Here to See The Original Article!!!

Given a set of non-overlapping intervals, insert a new interval into the intervals (meger if necesary).

You may assume the intervals were initially sorted according to theis start points.

Example 1:

Given intervals [[1,3],[6,9]], insert and merge [2,5] as [[1,5],[6,9]]

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10]

solution

  • If we know the the interval after inserting/merging new interval into intervals, the problem is solved.
  • Let’s decide the start point and end point of the new interval after inserting/merging.
  • How to find the new start point:
    • if start point is contained in an interval T of intervals. then new start point is the start point of T.
    • if start point is not contained by any itnerval of intervals, then new start point is the same as it was.
  • How to find the new end point.
    • if end point is contained in an interval T of intervals. then new ned point is the end point of T.
    • otherwise, the new end point is the same as it was.
  • output the result
    • for each interval in intervals, if it is contained in the new interval, ignore it because it was used to merge into the new interval.
    • if we find interval with start point is more than the endpoint of new interval, it’s time to insert the new interval into our result.

code

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> ret;
        if (intervals.empty()) {
            ret.push_back(newInterval);
        } else {
            Interval final;
            int n = intervals.size();
            int start = newInterval.start;
            int end = newInterval.end;
            if (start < intervals[0].start) {
                final.start = start;
            }
            if (start > intervals[n - 1].end) {
                final.start = start;
            }
            final.end = end;
            for (int i = 0; i < n; ++i) {
                // decide start
                if (start >= intervals[i].start && start <= intervals[i].end) {
                    final.start = intervals[i].start;
                }
                if (i >= 1 && start > intervals[i - 1].end && start < intervals[i].start) {
                    final.start = start;
                    if (start == intervals[i - 1].end) {
                        final.start = intervals[i - 1].start;
                    }
                }
                //decide end
                if (end >= intervals[i].start && end <= intervals[i].end) {
                    final.end = intervals[i].end;
                }
            }
            std::cout << "final: [" << final.start << ", " << final.end << "]" << std::endl;
            // output result
            bool add = false;
            for (int i = 0; i < n; ++i) {
                if (final.start <= intervals[i].start && final.end >= intervals[i].end) {
                    continue;
                }
                if (!add && intervals[i].start > final.end) {
                    ret.push_back(final);
                    add = true;
                }
                ret.push_back(intervals[i]);
            }
            if (!add) {
                ret.push_back(final);
            }
        }
        return ret;
    }
};







New