Saturday, July 11, 2015

LeetCode [57] Insert Interval

57. Insert Interval
Hard
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:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
========
* use upper_bound to find the the range of merged interval
* the sort in the last step can be optimized by delicate insertions.
========
 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution
{
  public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        vector<vector<int>> ret;
        int lb, ub;

        //find lower bound of merged new interval
        // |--prev(lv)--|     |--lv--|
        //          |--newIntv--|
        //lv is the first interval pass newInterval[0]. 
        //INT_MAX makes upper_bound return a vector with strickly greater first value
        auto lv = upper_bound(intervals.begin(), intervals.end(), vector<int>{newInterval[0], INT_MAX});
        if (lv == intervals.begin())
        {
            lb = newInterval[0];
        }
        else
        {
            lv = prev(lv);
            if ((*lv)[1] >= newInterval[0])
                lb = (*lv)[0];
            else
                lb = newInterval[0];
        }

        //find upper bound of the merged interval
        // |--prev(uv)--|             |--uv--|
        //          |--newIntv--|
        //lv is the first interval pass newInterval[1]. 
        auto uv = upper_bound(intervals.begin(), intervals.end(), vector<int>{newInterval[1], INT_MAX});
        if (uv == intervals.begin())
        {
            ub = newInterval[1];
        }
        else
        {
            uv = prev(uv);
            ub = max(newInterval[1], (*uv)[1]);
        }

        for(auto i:intervals)
        {
            if(i[1]<lb || i[1]>ub) ret.push_back(i);
        }
        ret.push_back(vector<int>{lb, ub});
        sort(ret.begin(), ret.end());

        return ret;
    }
};
======== legend ======== 
 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
27
28
29
30
31
32
33
34
35
36
37
//C++: method1 596ms
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool compare(const Interval &a, const Interval &b){
  return a.start<b.start;
}
  
class Solution {
public:
    vector<interval> merge(vector<interval>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        vector<interval> res;
        int n = intervals.size();
        int i = 0;
        while(i<n){
            int j = i+1;
            while(j<n && intervals[i].end>=intervals[j].start){
                intervals[i].end = max(intervals[i].end, intervals[j].end);
                j++;
            }
            res.push_back(intervals[i]);
            i = j;
        }
        return res;
    }
    vector<interval> insert(vector<interval>& intervals, Interval newInterval) {
        intervals.push_back(newInterval);
        return merge(intervals);
    }
};


 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
27
28
29
30
31
32
33
34
35
36
/**
 * 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> res;
        int n = intervals.size();
        int i=0;

        while(i<n && intervals[i].end<newInterval.start){
            res.push_back(intervals[i++]);
        }

        if(i==n || newInterval.end<intervals[i].start){
            res.push_back(newInterval);
        }else{
            int start = i++;
            while(i<n && newInterval.end>=intervals[i].start) i++;
            int end = i-1;

            newInterval.start = min(newInterval.start, intervals[start].start);
            newInterval.end = max(newInterval.end, intervals[end].end);
            res.push_back(newInterval);
        }

        while(i<n) res.push_back(intervals[i++]);
        return res;
    }
};


 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * 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> res;
        int n = intervals.size();
        if(n==0){res.push_back(newInterval); return res;}

        int i=0;
        vector<interval>::iterator it=intervals.begin();
        //|---0--| ... |---i--|
        //                       |----newInt------|
        while(i<n && intervals[i].end<newInterval.start){
            res.push_back(intervals[i++]);
        }
        
        //newIntervals is left alone
        if(i==n){
            res.push_back(newInterval); 
            return res;
        }
        
        //                          |----i-----|
        //|-----newInt-------|
        if(newInterval.end<intervals[i].start){
            res.push_back(newInterval);
            res.insert(res.end(), it+i, it+n);
            return res;
        }

        //          |----i-----|       |----i-----|
        //|-----newInt---|        or        |-----newInt-------| 
        //a                    b       a                       b
        int a = min(intervals[i].start, newInterval.start);
        int b = max(intervals[i].end, newInterval.end);            
        for(++i;i<n;++i){
            if(b<intervals[i].start){
                Interval intv(a, b);
                res.push_back(intv);
                res.insert(res.end(), it+i, it+n);
                break;
            }else{
                b = max(intervals[i].end, b);
            }
        }
        if(i==n){
            Interval intv(a, b);
            res.push_back(intv);                            
        }

        return res;
    }
};


 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
27
28
29
30
31
32
33
//Java
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        int i = 0;
        int start = newInterval[0];
        int end = newInterval[1];
        List<int[]> list = new ArrayList<>();

        while(i<n && intervals[i][1]<start){
            list.add(intervals[i]);
            i++;
        }

        while(i<n && intervals[i][0]<=end){
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        list.add(new int[]{start, end});

        while(i<n){
            list.add(intervals[i]);
            i++;
        }
        
        int[][] res = new int[list.size()][2];
        for(int k=0; k<list.size(); ++k){
            res[k] = list.get(k);
        }
        return res;
    }
}


 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        List<int[]> list = new ArrayList<>();
        int l = lastEndBeforeNewStart(intervals, newInterval[0]);
        int r = firstStartBeforeNewEnd(intervals, newInterval[1]);
        int i = 0;
        while(i<=l){
            list.add(intervals[i++]);
        }
        int start = newInterval[0], end = newInterval[1];
        while(i<r){
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        list.add(new int[]{start, end});
        while(i<n){
            list.add(intervals[i++]);
        }
        return list.toArray(new int[0][]);
    }

    int lastEndBeforeNewStart(int[][] intervals, int newStart){
        int n = intervals.length;
        int l = 0, r = n-1;
        while(l<=r){
            int m = (l+r)/2;
            if(intervals[m][1]<newStart && (m==r || intervals[m+1][1]>=newStart)){
                return m;
            }else if(intervals[m][1]<newStart){
                l = m+1;
            }else{
                r = m-1;
            }
        }
        return -1;
    }

    int firstStartBeforeNewEnd(int[][] intervals, int newEnd){
        int n = intervals.length;
        int l = 0, r = n-1;
        while(l<=r){
            int m = (l+r)/2;
            if(intervals[m][0]>newEnd && (m==l||intervals[m-1][0]<=newEnd)){
                return m;
            }else if(intervals[m][0]>newEnd){
                r = m-1;
            }else{
                l = m+1;
            }
        }
        return n;
    }
}


 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
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0], end = newInterval[1];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int[] i : intervals){
            int u = i[0], v = i[1];
            map.put(u, v);
        }

        //[l, r], find max l s.t. l<=start
        Map.Entry<Integer, Integer> lEntry = map.floorEntry(start);
        if(lEntry!=null && lEntry.getValue()>=start){
            start = lEntry.getKey();
        }

        //[l, r] find min l s.t. l<=end
        Map.Entry<Integer, Integer> rEntry = map.floorEntry(end);
        if(rEntry!=null && rEntry.getValue()>=end){
            end = rEntry.getValue();
        }

        Map<Integer, Integer> submap = map.subMap(start, true, end, true);
        Set<Integer> set = new HashSet<>(submap.keySet());
        map.keySet().removeAll(set);
        map.put(start, end);

        int[][] ret = new int[map.size()][2];
        int i = 0;
        for(Map.Entry<Integer, Integer> en : map.entrySet()){
            ret[i][0] = en.getKey();
            ret[i][1] = en.getValue();
            i++;
        }
        
        return ret;
    }
}
Posted by at
Labels: ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)