Problem:
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in 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].
Idea:
Find the position of the new interval, insert it into the list and call MergeIntervals in LeetCode 56
Solution:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Runtime: 16 ms class Solution { public: vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { auto it = intervals.begin(); while (it != intervals.end() && newInterval.start > it->start) ++it; intervals.insert(it, newInterval); // Merge intervals without sorting vector<Interval> ans; for (const auto& interval : intervals) { if (ans.empty() || interval.start > ans.back().end) { ans.push_back(interval); } else { ans.back().end = max(ans.back().end, interval.end); } } return ans; } }; |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
""" Author: Huahua Runtime: 78 ms """ class Solution(object): def insert(self, intervals, newInterval): index = len(intervals) for i in range(len(intervals)): if newInterval.start < intervals[i].start: index = i break intervals.insert(index, newInterval) ans = [] for interval in intervals: if not ans or interval.start > ans[-1].end: ans.append(interval) else: ans[-1].end = max(ans[-1].end, interval.end) return ans |
Solution 2:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua // Runtime: 13 ms class Solution { public: vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { vector<Interval> l; vector<Interval> r; int start = newInterval.start; int end = newInterval.end; for (const Interval& interval : intervals) { if (interval.end < start) l.push_back(interval); else if (interval.start > end) r.push_back(interval); else { start = min(start, interval.start); end = max(end, interval.end); } } vector<Interval> ans(std::move(l)); ans.emplace_back(start, end); ans.insert(ans.end(), r.begin(), r.end()); return ans; } }; |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
""" Author: Huahua Runtime: 68 ms """ class Solution(object): def insert(self, intervals, newInterval): start, end = newInterval.start, newInterval.end l, r = [], [] for interval in intervals: if interval.end < start: l += interval, elif interval.start > end: r += interval, else: start = min(start, interval.start) end = max(end, interval.end) return l + [Interval(start, end)] + r |
Related problems:
