Title: Merge Intervals Source: leetcode.com
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
Java solution
|
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 97 98 99 100 |
/* https://leetcode.com/problems/merge-intervals/ */ import java.util.List; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Stack; public class MergeIntervals { public List<Interval> merge(List<Interval> intervals) { this.sort(intervals); Stack<Interval> stack = new Stack<>(); for(Interval interval : intervals) { if(stack.isEmpty()) { stack.push(interval); continue; } Interval i = stack.peek(); if(interval.start <= i.start) { //System.out.println("1"); if((i.start < interval.end && interval.end <= i.end) || (i.end < interval.end)) { stack.pop(); int s = interval.start < i.start ? interval.start : i.start; int e = interval.end < i.end ? i.end:interval.end; stack.push(new Interval(s, e)); } } else if(i.start < interval.start) { //System.out.println("2"); if(interval.start <= i.end) { stack.pop(); int e = interval.end < i.end ? i.end : interval.end; stack.push(new Interval(i.start, e)); } else { stack.push(interval); } } } ArrayList<Interval> a = new ArrayList<>(stack); return a; } public void sort(List<Interval> intervals) { Collections.sort(intervals, new Comparator<Interval>(){ public int compare(Interval i1, Interval i2) { return i1.start-i2.start; } }); } public void print(List<Interval> intervals) { for(Interval interval : intervals) { System.out.println("["+interval.start+", "+interval.end+"]"); } } public static void main(String args[]) { MergeIntervals mi = new MergeIntervals(); List<Interval> list = new ArrayList<>(); list.add(new Interval(1, 3)); list.add(new Interval(2, 6)); list.add(new Interval(8, 10)); list.add(new Interval(9, 11)); list.add(new Interval(15, 18)); //mi.print(list); mi.print(mi.merge(list)); } } class Interval { int start; int end; Interval() { start = 0; end = 0; } Interval(int s, int e) { start = s; end = e; } } |