FilesExpand file tree

 master

/

InsertInterval.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

96 lines (89 loc) · 2.98 KB

 master

/

InsertInterval.java

Copy path

Top

File metadata and controls

• Code
• Blame

96 lines (89 loc) · 2.98 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package array;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

/**

* Created by gouthamvidyapradhan on 15/12/2017. Given a set of non-overlapping intervals, insert a

* new interval into the intervals (merge if necessary).

*

* <p>You may assume that the intervals were initially sorted according to their start times.

*

* <p>Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

*

* <p>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].

*

* <p>This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

*

* <p>Solution: O(n): Iterate through each interval and check for each overlapping case

*/

public class InsertInterval {

public static class Interval {

int start;

int end;

Interval() {

start = 0;

end = 0;

}

Interval(int s, int e) {

start = s;

end = e;

}

}

/**

* Main method

*

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception {

Interval i1 = new Interval(1, 2);

Interval i2 = new Interval(3, 5);

Interval i3 = new Interval(6, 7);

Interval i4 = new Interval(8, 10);

Interval i5 = new Interval(12, 16);

List<Interval> list = Arrays.asList(i1, i2, i3, i4, i5);

List<Interval> result = new InsertInterval().insert(list, new Interval(2, 5));

result.stream().map(x -> x.start + " " + x.end).forEach(System.out::println);

}

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {

List<Interval> result = new ArrayList<>();

for (int i = 0, l = intervals.size(); i < l; i++) {

Interval curr = intervals.get(i);

if (newInterval.start >= curr.start && newInterval.end <= curr.end) {

insertRest(intervals, result, i);

return result; // easy case

} else if (newInterval.start < curr.start && newInterval.end > curr.end) {

newInterval = new Interval(newInterval.start, newInterval.end);

// merge and continue

} else if (newInterval.start >= curr.start

&& newInterval.start <= curr.end

&& newInterval.end > curr.end) {

newInterval = new Interval(curr.start, newInterval.end);

// merge and continue

} else if (newInterval.start < curr.start

&& newInterval.end >= curr.start

&& newInterval.end <= curr.end) {

Interval newI = new Interval(newInterval.start, curr.end);

result.add(newI);

insertRest(intervals, result, i + 1);

return result;

} else if (newInterval.start > curr.end) {

result.add(curr);

} else {

result.add(newInterval);

insertRest(intervals, result, i);

return result;

}

}

result.add(newInterval);

return result;

}

private void insertRest(List<Interval> intervals, List<Interval> result, int i) {

int l = intervals.size();

while (i < l) {

result.add(intervals.get(i));

i++;

}

}

}