Screenshot from 2016-01-11 18:59:19.png
My code:
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
ArrayList<Interval> ret = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) {
ret.add(newInterval);
return ret;
}
if (newInterval == null)
return intervals;
ret.add(newInterval);
for (int i = 0; i < intervals.size(); i++) {
Interval originInterval = intervals.get(i);
int originStart = originInterval.start;
int originEnd = originInterval.end;
for (int j = ret.size() - 1; j >= -1; j--) {
if (j == -1) { // if it is minimun, insert at the beginning whose index is 0
ret.add(0, originInterval);
break;
}
Interval retInterval = ret.get(j);
int retStart = retInterval.start;
int retEnd = retInterval.end;
if (originStart > retEnd) { // if bigger than this element, insert behind it, so the inserting index should be j + 1
ret.add(j + 1, originInterval);
break;
}
else if (originEnd < retStart) { // if smaller than this element, visit the front elements to compare
continue;
}
else {
retInterval.start = Math.min(originStart, retStart); // if needs merge, change values so to merge
retInterval.end = Math.max(originEnd, retEnd);
break;
}
}
}
return ret;
}
}
这道题木之前做过，但应该没有写文章。但还有印象。
自己写了出来。
其实就是一个插入 + merge的过程。
怎么样才能让这个过程足够简单并且可以用程序实现。
This is the question we need to deal with.
Fuck off!
如果就在 intervals上实现这么一个过程。
那么会很复杂，思考起来。
你想，
你如何判断什么时候，该merge？
那么，我现在的思路是，
假设:
originStart, originEnd 为intervals其中某个元素的起始。
newStart, newEnd 为需要插入元素的起始。
So,
for (int i = 0; i < intervals.size(); i++) {
if (newStart > originEnd)
continue;
else if (newEnd < originStart)
intervals.add(i, newInterval);
else {
}
}
想着想着，突然发现也可以做，而且更加简洁，只要一次遍历就行。。。
于是写了出来。
我他妈真他妈，变强了，草。
**
但是奇怪的一点，
我觉得这么做速度更快，但是LJ上显示，速度反而更慢了，怎么会呢？不能理解。到时候得问下人。
**
我一开始的做法就是新建一个集合，然后先把newInterval放进去，然后把intervals里面的元素一个个有序放进去，需要merge的地方就merge，然后就写出来了。
第二个做法就是针对intervals来做。
思路在上面的伪代码上基本上也写明白了。
但是，为什么速度反而慢了很多呢？
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
ArrayList<Interval> ret = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) {
ret.add(newInterval);
return ret;
}
if (newInterval == null)
return intervals;
ret.add(newInterval);
int newStart = newInterval.start;
int newEnd = newInterval.end;
int i = 0;
for (; i < intervals.size(); i++) {
int originStart = intervals.get(i).start;
int originEnd = intervals.get(i).end;
if (newStart > originEnd)
continue;
else if (newEnd < originStart) {
intervals.add(i, new Interval(newStart, newEnd));
break;
}
else { // update newStart, newEnd,remove origin element, later will add updated element(merge)
newStart = Math.min(originStart, newStart);
newEnd = Math.max(originEnd, newEnd);
intervals.remove(i);
i--;
}
}
if (i == intervals.size())
intervals.add(new Interval(newStart, newEnd));
return intervals;
}
}
这道题目级别是hard，但是现在想来没有什么难度。
DP才是王道啊。
Anyway, Good luck, Richardo!
More efficient solution:
My code:
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
ArrayList<Interval> ret = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) {
ret.add(newInterval);
return ret;
}
for (int i = 0; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.end < newInterval.start) {
ret.add(curr);
}
else if (curr.start > newInterval.end) {
ret.add(newInterval);
newInterval = curr;
}
else if (curr.start <= newInterval.start || curr.end >= newInterval.end) {
newInterval = new Interval(Math.min(curr.start, newInterval.start), Math.max(curr.end, newInterval.end));
}
}
ret.add(newInterval);
return ret;
}
}
Anyway, Good luck, Richardo!
My code:
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> ret = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) {
ret.add(newInterval);
return ret;
}
else if (newInterval == null) {
return intervals;
}
Interval curr = newInterval;
for (int i = intervals.size() - 1; i >= 0; i--) {
Interval pre = intervals.get(i);
if (pre.end < curr.start) {
intervals.add(i + 1, curr);
return intervals;
}
else if (pre.start <= curr.start) {
pre.end = Math.max(pre.end, curr.end);
return intervals;
}
else if (pre.start <= curr.end) {
pre.start = curr.start;
pre.end = Math.max(pre.end, curr.end);
curr = pre;
intervals.remove(i);
}
else {
continue;
}
}
intervals.add(0, curr);
return intervals;
}
}
和merge interval差不多，是他的一个子问题。
Anyway, Good luck, Richardo! -- 09/02/2016
My code:
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> ret = new ArrayList<Interval>();
int i = 0;
for (; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.end < newInterval.start) {
ret.add(curr);
continue;
}
else {
break;
}
}
for (; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.start > newInterval.end) {
break;
}
newInterval.start = Math.min(newInterval.start, curr.start);
newInterval.end = Math.max(newInterval.end, curr.end);
}
ret.add(newInterval);
for (; i < intervals.size(); i++) {
ret.add(intervals.get(i));
}
return ret;
}
}
reference:
https://discuss.leetcode.com/topic/7808/short-and-straight-forward-java-solution
这个做法比之前的做法更高效，可以保证 O(n) 的复杂度
Anyway, Good luck, Richardo! -- 10/15/2016
