leetcode/InsertInterval.java at master · Susheng/leetcode · GitHub

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
/**
 * 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:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 *
 * 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].
 *
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;

publicclassInsertInterval {
publicclassIntervalCmpimplementsComparator<Interval> {

@Override
publicintcompare(Intervali1, Intervali2) {
if (i1.start < i2.start) {
return -1;
 }
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
 }
return1;
 }

	}

publicArrayList<Interval> insert(ArrayList<Interval> intervals,
IntervalnewInterval) {
intervals.add(newInterval);
Interval[] arr = newInterval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, newIntervalCmp());
intervals.clear();
intstart = arr[0].start;
intend = arr[0].end;
for (inti = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
 } else {
intervals.add(newInterval(start, end));
start = arr[i].start;
end = arr[i].end;
 }
 }
intervals.add(newInterval(start, end));
returnintervals;
	}
}
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
/**
 * 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:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 *
 * 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].
 *
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;

publicclassInsertInterval {
publicclassIntervalCmpimplementsComparator<Interval> {

@Override
publicintcompare(Intervali1, Intervali2) {
if (i1.start < i2.start) {
return -1;
 }
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
 }
return1;
 }

	}

publicArrayList<Interval> insert(ArrayList<Interval> intervals,
IntervalnewInterval) {
intervals.add(newInterval);
Interval[] arr = newInterval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, newIntervalCmp());
intervals.clear();
intstart = arr[0].start;
intend = arr[0].end;
for (inti = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
 } else {
intervals.add(newInterval(start, end));
start = arr[i].start;
end = arr[i].end;
 }
 }
intervals.add(newInterval(start, end));
returnintervals;
	}
}
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
/**
 * 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:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 *
 * 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].
 *
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;

publicclassInsertInterval {
publicclassIntervalCmpimplementsComparator<Interval> {

@Override
publicintcompare(Intervali1, Intervali2) {
if (i1.start < i2.start) {
return -1;
 }
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
 }
return1;
 }

	}

publicArrayList<Interval> insert(ArrayList<Interval> intervals,
IntervalnewInterval) {
intervals.add(newInterval);
Interval[] arr = newInterval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, newIntervalCmp());
intervals.clear();
intstart = arr[0].start;
intend = arr[0].end;
for (inti = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
 } else {
intervals.add(newInterval(start, end));
start = arr[i].start;
end = arr[i].end;
 }
 }
intervals.add(newInterval(start, end));
returnintervals;
	}
}
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
/**
 * 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:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 *
 * 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].
 *
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;

publicclassInsertInterval {
publicclassIntervalCmpimplementsComparator<Interval> {

@Override
publicintcompare(Intervali1, Intervali2) {
if (i1.start < i2.start) {
return -1;
 }
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
 }
return1;
 }

	}

publicArrayList<Interval> insert(ArrayList<Interval> intervals,
IntervalnewInterval) {
intervals.add(newInterval);
Interval[] arr = newInterval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, newIntervalCmp());
intervals.clear();
intstart = arr[0].start;
intend = arr[0].end;
for (inti = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
 } else {
intervals.add(newInterval(start, end));
start = arr[i].start;
end = arr[i].end;
 }
 }
intervals.add(newInterval(start, end));
returnintervals;
	}
}
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
/**
 * 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:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 *
 * 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].
 *
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;

publicclassInsertInterval {
publicclassIntervalCmpimplementsComparator<Interval> {

@Override
publicintcompare(Intervali1, Intervali2) {
if (i1.start < i2.start) {
return -1;
 }
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
 }
return1;
 }

	}

publicArrayList<Interval> insert(ArrayList<Interval> intervals,
IntervalnewInterval) {
intervals.add(newInterval);
Interval[] arr = newInterval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, newIntervalCmp());
intervals.clear();
intstart = arr[0].start;
intend = arr[0].end;
for (inti = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
 } else {
intervals.add(newInterval(start, end));
start = arr[i].start;
end = arr[i].end;
 }
 }
intervals.add(newInterval(start, end));
returnintervals;
	}
}
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
/**
 * 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:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 *
 * 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].
 *
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;

publicclassInsertInterval {
publicclassIntervalCmpimplementsComparator<Interval> {

@Override
publicintcompare(Intervali1, Intervali2) {
if (i1.start < i2.start) {
return -1;
 }
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
 }
return1;
 }

	}

publicArrayList<Interval> insert(ArrayList<Interval> intervals,
IntervalnewInterval) {
intervals.add(newInterval);
Interval[] arr = newInterval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, newIntervalCmp());
intervals.clear();
intstart = arr[0].start;
intend = arr[0].end;
for (inti = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
 } else {
intervals.add(newInterval(start, end));
start = arr[i].start;
end = arr[i].end;
 }
 }
intervals.add(newInterval(start, end));
returnintervals;
	}
}
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
/**
 * 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:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 *
 * 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].
 *
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;

publicclassInsertInterval {
publicclassIntervalCmpimplementsComparator<Interval> {

@Override
publicintcompare(Intervali1, Intervali2) {
if (i1.start < i2.start) {
return -1;
 }
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
 }
return1;
 }

	}

publicArrayList<Interval> insert(ArrayList<Interval> intervals,
IntervalnewInterval) {
intervals.add(newInterval);
Interval[] arr = newInterval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, newIntervalCmp());
intervals.clear();
intstart = arr[0].start;
intend = arr[0].end;
for (inti = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
 } else {
intervals.add(newInterval(start, end));
start = arr[i].start;
end = arr[i].end;
 }
 }
intervals.add(newInterval(start, end));
returnintervals;
	}
}
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
/**
 * 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:
 * Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
 *
 * 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].
 *
 * This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;

publicclassInsertInterval {
publicclassIntervalCmpimplementsComparator<Interval> {

@Override
publicintcompare(Intervali1, Intervali2) {
if (i1.start < i2.start) {
return -1;
 }
if (i1.start == i2.start && i1.end <= i2.end) {
return -1;
 }
return1;
 }

	}

publicArrayList<Interval> insert(ArrayList<Interval> intervals,
IntervalnewInterval) {
intervals.add(newInterval);
Interval[] arr = newInterval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, newIntervalCmp());
intervals.clear();
intstart = arr[0].start;
intend = arr[0].end;
for (inti = 1; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
 } else {
intervals.add(newInterval(start, end));
start = arr[i].start;
end = arr[i].end;
 }
 }
intervals.add(newInterval(start, end));
returnintervals;
	}
}