Wednesday, May 15, 2019

Lintcode 577. Merge K Sorted Interval Lists

Merge K sorted interval lists into one sorted interval list. You need to merge overlapping intervals too.

Example

Example1
Input: [
  [(1,3),(4,7),(6,8)],
  [(1,2),(9,10)]
]
Output: [(1,3),(4,8),(9,10)]
Example2
Input: [
  [(1,2),(5,6)],
  [(3,4),(7,8)]
]
Output: [(1,2),(3,4),(5,6),(7,8)]
Code (Java)
?
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param intervals: the given k sorted interval lists
     * @return:  the new sorted interval list
     */
    public List<Interval> mergeKSortedIntervalLists(List<List<Interval>> intervals) {
        // write your code here
        List<Interval> ans = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return ans;
        }
 
        return mergeHelper(0, intervals.size() - 1, intervals);
    }
 
    private List<Interval> mergeHelper(int start, int end, List<List<Interval>> intervals) {
        if (start == end) {
            return intervals.get(start);
        }
 
        int mid = start + (end - start) / 2;
 
        List<Interval> left = mergeHelper(start, mid, intervals);
        List<Interval> right = mergeHelper(mid + 1, end, intervals);
 
        return mergeTwoLists(left, right);
    }
 
    private List<Interval> mergeTwoLists(List<Interval> list1, List<Interval> list2) {
        int i = 0;
        int j = 0;
        Interval prev = null;
        List<Interval> ans = new ArrayList<>();
 
        while (i < list1.size() && j < list2.size()) {
            Interval curr = null;
            Interval v1 = list1.get(i);
            Interval v2 = list2.get(j);
 
            if (v1.start < v2.start) {
                curr = v1;
                prev = merge(ans, prev, curr);
                i++;
            } else {
                curr = v2;
                prev = merge(ans, prev, curr);
                j++;
            }
        }
 
        while (i < list1.size()) {
            Interval curr = list1.get(i);
            prev = merge(ans, prev, curr);
            i++;
        }
 
        while (j < list2.size()) {
            Interval curr = list2.get(j);
            prev = merge(ans, prev, curr);
            j++;
        }
 
        if (prev != null) {
            ans.add(prev);
        }
 
        return ans;
    }
 
    private Interval merge(List<Interval> ans, Interval prev, Interval curr) {
        if (prev == null) {
            prev = curr;
            return prev;
        }
 
        if (prev.end < curr.start) {
            ans.add(prev);
            prev = curr;
        }
 
        prev.end = Math.max(prev.end, curr.end);
 
        return prev;
    }
}
Posted by at
Labels:

1 comment:

  1. profilerahulMarch 29, 2020 at 3:38 PM

    Modified Solution :

    import java.util.*;
    class Interval
    {
    int start,end;
    Interval(int start, int end)
    {
    this.start=start;
    this.end=end;
    }
    public String toString()
    {
    return this.start + " " + this.end ;
    }

    }

    class SortbyEnd implements Comparator
    {
    // Used for sorting in ascending order of
    // roll number
    public int compare(Interval a, Interval b)
    {
    return a.end - b.end;
    }
    }



    class MyClass
    {
    public static void main(String args[]){
    List list = new ArrayList();
    //list.add(new Interval(1,2));list.add(new Interval(4,7));list.add(new Interval(1,3));list.add(new Interval(6,8));list.add(new Interval(9,10));
    list.add(new Interval(1,2));list.add(new Interval(5,6));list.add(new Interval(3,4));list.add(new Interval(7,8));
    Collections.sort(list, new SortbyEnd());
    System.out.println(list);
    test(list);
    }

    static void test(List list)
    {
    int a=0,b=0;
    List ans = new ArrayList();
    for(int i=0;i list.get(i+1).start)
    {
    a=list.get(i).start;
    b=list.get(i+1).end;
    ans.add(new Interval(a,b));
    i+=1;
    }
    else{
    ans.add(new Interval(list.get(i).start,list.get(i).end));
    }

    }
    System.out.println(ans);
    }
    }

    ReplyDelete

Subscribe to: Post Comments (Atom)