8000 add 57 · deepakavs/Leetcode@b01f56d · GitHub
[go: up one dir, main page]
Skip to content < 8000 span data-view-component="true" class="progress-pjax-loader Progress position-fixed width-full">

Commit b01f56d

Browse files
fishercoder1534fishercoder1534
committed
add 57
1 parent 80bf1d9 commit b01f56d

File tree

5 files changed

+187
-18
lines changed

5 files changed

+187
-18
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -467,6 +467,7 @@ Your ideas/fixes/algorithms are more than welcome!
467467
|60|[Permutation Sequence](https://leetcode.com/problems/permutation-sequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/PermutationSequence.java)|?|?|Medium|
468468
|59|[Spiral Matrix II](https://leetcode.com/problems/spiral-matrix-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/SpiralMatrixII.java)|O(n)|O(n)|Medium|
469469
|58|[Length of Last Word](https://leetcode.com/problems/length-of-last-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/LengthofLastWord.java)|O(n)|O(1)|Easy|
470+
|57|[Insert Intervals](https://leetcode.com/problems/insert-interval/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_57.java)|O(n)|O(1)|Hard| Array, Sort
470471
|56|[Merge Intervals](https://leetcode.com/problems/merge-intervals/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_56.java)|O(n*logn)|O(1)|Medium| Array, Sort
471472
|55|[Jump Game](https://leetcode.com/problems/jump-game/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_55.java)|O(n)|O(1)|Medium| Greedy
472473
|54|[Spiral Matrix](https://leetcode.com/problems/spiral-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_54.java)|O(m*n)|O(m*n)|Medium| Array

‎src/main/java/com/fishercoder/common/classes/Interval.java

Lines changed: 20 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,8 +9,27 @@ public Interval() {
99
start = 0;
1010
end = 0;
1111
}
12-
12+
13+
@Override
14+
public boolean equals(Object o) {
15+
if (this == o) return true;
16+
if (!(o instanceof Interval)) return false;
17+
18+
Interval interval = (Interval) o;
19+
20+
if (start != interval.start) return false;
21+
return end == interval.end;
22+
}
23+
24+
@Override
25+
public int hashCode() {
26+
int result = start;
27+
result = 31 * result + end;
28+
return result;
29+
}
30+
1331
public Interval(int s, int e){
32+
1433
this.start = s;
1534
this.end = e;
1635
}

‎src/main/java/com/fishercoder/solutions/InsertInterval.java

Lines changed: 0 additions & 17 deletions
This file was deleted.

‎src/main/java/com/fishercoder/solutions/_57.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.Interval;
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
8+
/**
9+
* 57. Insert Interval
10+
*
11+
* Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
12+
13+
You may assume that the intervals were initially sorted according to their start times.
14+
15+
Example 1:
16+
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
17+
18+
Example 2:
19+
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
20+
21+
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
22+
*/
23+
public class _57 {
24+
25+
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
26+
List<Interval> result = new ArrayList<>();
27+
int i = 0;
28+
// add all the intervals ending before newInterval starts
29+
while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
30+
result.add(intervals.get(i++));
31+
}
32+
// merge all overlapping intervals to one considering newInterval
33+
while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
34+
newInterval = new Interval( // we could mutate newInterval here also
35+
Math.min(newInterval.start, intervals.get(i).start),
36+
Math.max(newInterval.end, intervals.get(i).end));
37+
i++;
38+
}
39+
result.add(newInterval);
40+
// add all the rest
41+
while (i < intervals.size()) {
42+
result.add(intervals.get(i++));
43+
}
44+
return result;
45+
}
46+
47+
}

‎src/test/java/com/fishercoder/_57Test.java

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.Interval;
4+
import com.fishercoder.common.utils.CommonUtils;
5+
import com.fishercoder.solutions._57;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import java.util.ArrayList;
10+
import java.util.Arrays;
11+
import java.util.List;
12+
13+
import static org.junit.Assert.assertEquals;
14+
15+
/**
16+
* Created by stevesun on 6/14/17.
17+
*/
18+
public class _57Test {
19+
private static _57 test;
20+
private static List<Interval> intervals;
21+
private static List<Interval> expected;
22+
private static List<Interval> actual;
23+
24+
@BeforeClass
25+
public static void setup(){
26+
test = new _57();
27+
}
28+
29+
@Test
30+
public void test1(){
31+
intervals = new ArrayList<>(Arrays.asList(new Interval(1,3), new Interval(6,9)));
32+
expected = new ArrayList<>(Arrays.asList(new Interval(1,5), new Interval(6,9)));
33+
CommonUtils.printIntervals(intervals);
34+
actual = test.insert(intervals, new Interval(2,5));
35+
CommonUtils.printIntervals(actual);
36+
assertEquals(expected, actual);
37+
}
38+
39+
40+
@Test
41+
public void test2(){
42+
intervals = new ArrayList<>(Arrays.asList(new Interval(1,2), new Interval(3,5), new Interval(6,7), new Interval(8,10), new Interval(12,16)));
43+
CommonUtils.printIntervals(intervals);
44+
expected = new ArrayList<>(Arrays.asList(new Interval(1,2), new Interval(3,10), new Interval(12,16)));
45+
actual = test.insert(intervals, new Interval(4,9));
46+
CommonUtils.printIntervals(actual);
47+
assertEquals(expected, actual);
48+
}
49+
50+
@Test
51+
public void test3(){
52+
intervals = new ArrayList<>(Arrays.asList(new Interval(1,5)));
53+
CommonUtils.printIntervals(intervals);
54+
expected = new ArrayList<>(Arrays.asList(new Interval(1,5)));
55+
actual = test.insert(intervals, new Interval(2,3));
56+
CommonUtils.printIntervals(actual);
57+
assertEquals(expected, actual);
58+
}
59+
60+
@Test
61+
public void test4(){
62+
intervals = new ArrayList<>(Arrays.asList());
63+
CommonUtils.printIntervals(intervals);
64+
expected = new ArrayList<>(Arrays.asList(new Interval(5,7)));
65+
actual = test.insert(intervals, new Interval(5,7));
66+
CommonUtils.printIntervals(actual);
67+
assertEquals(expected, actual);
68+
}
69+
70+
@Test
71+
public void test5(){
72+
intervals = new ArrayList<>(Arrays.asList(new Interval(1,5)));
73+
expected = new ArrayList<>(Arrays.asList(new Interval(1,5), new Interval(6,8)));
74+
CommonUtils.printIntervals(intervals);
75+
actual = test.insert(intervals, new Interval(6,8));
76+
CommonUtils.printIntervals(actual);
77+
assertEquals(expected, actual);
78+
}
79+
80+
@Test
81+
public void test6(){
82+
intervals = new ArrayList<>(Arrays.asList(new Interval(1,5)));
83+
expected = new ArrayList<>(Arrays.asList(new Interval(0,5)));
84+
CommonUtils.printIntervals(intervals);
85+
actual = test.insert(intervals, new Interval(0,3));
86+
CommonUtils.printIntervals(actual);
87+
assertEquals(expected, actual);
88+
}
89+
90+
@Test
91+
public void test7(){
92+
intervals = new ArrayList<>(Arrays.asList(new Interval(1,5)));
93+
expected = new ArrayList<>(Arrays.asList(new Interval(0,0), new Interval(1,5)));
94+
CommonUtils.printIntervals(intervals);
95+
actual = test.insert(intervals, new Interval(0,0));
96+
CommonUtils.printIntervals(actual);
97+
assertEquals(expected, actual);
98+
}
99+
100+
@Test
101+
public void test8(){
102+
intervals = new ArrayList<>(Arrays.asList(new Interval(2,5), new Interval(6,7), new Interval(8,9)));
103+
expected = new ArrayList<>(Arrays.asList(new Interval(0,1), new Interval(2,5), new Interval(6,7), new Interval(8,9)));
104+
CommonUtils.printIntervals(intervals);
105+
actual = test.insert(intervals, new Interval(0,1));
106+
CommonUtils.printIntervals(actual);
107+
assertEquals(expected, actual);
108+
}
109+
110+
@Test
111+
public void test9(){
112+
intervals = new ArrayList<>(Arrays.asList(new Interval(2,4), new Interval(5,7), new Interval(8,10), new Interval(11,13)));
113+
expected = new ArrayList<>(Arrays.asList(new Interval(2,7), new Interval(8,10), new Interval(11,13)));
114+
CommonUtils.printIntervals(intervals);
115+
actual = test.insert(intervals, new Interval(3,6));
116+
CommonUtils.printIntervals(actual);
117+
assertEquals(expected, actual);
118+
}
119+
}

0 commit comments

Comments
 (0)
0