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;
}
}
這道題木之前做過(guò)雌隅，但應(yīng)該沒(méi)有寫文章。但還有印象。
自己寫了出來(lái)恰起。
其實(shí)就是一個(gè)插入 + merge的過(guò)程修械。
怎么樣才能讓這個(gè)過(guò)程足夠簡(jiǎn)單并且可以用程序?qū)崿F(xiàn)。
This is the question we need to deal with.
Fuck off!
如果就在 intervals上實(shí)現(xiàn)這么一個(gè)過(guò)程检盼。
那么會(huì)很復(fù)雜祠肥，思考起來(lái)。
你想梯皿，
你如何判斷什么時(shí)候仇箱，該merge？
那么东羹，我現(xiàn)在的思路是剂桥，
假設(shè):
originStart, originEnd 為intervals其中某個(gè)元素的起始。
newStart, newEnd 為需要插入元素的起始属提。
So,
for (int i = 0; i < intervals.size(); i++) {
if (newStart > originEnd)
continue;
else if (newEnd < originStart)
intervals.add(i, newInterval);
else {
}
}
想著想著权逗，突然發(fā)現(xiàn)也可以做，而且更加簡(jiǎn)潔冤议，只要一次遍歷就行斟薇。。恕酸。
于是寫了出來(lái)堪滨。
我他媽真他媽，變強(qiáng)了蕊温，草袱箱。
**
但是奇怪的一點(diǎn)，
我覺(jué)得這么做速度更快义矛，但是LJ上顯示发笔，速度反而更慢了，怎么會(huì)呢凉翻？不能理解了讨。到時(shí)候得問(wèn)下人。
**
我一開始的做法就是新建一個(gè)集合制轰，然后先把newInterval放進(jìn)去前计，然后把intervals里面的元素一個(gè)個(gè)有序放進(jìn)去，需要merge的地方就merge艇挨，然后就寫出來(lái)了残炮。
第二個(gè)做法就是針對(duì)intervals來(lái)做。
思路在上面的偽代碼上基本上也寫明白了缩滨。
但是，為什么速度反而慢了很多呢？
/**
* 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;
}
}
這道題目級(jí)別是hard脉漏，但是現(xiàn)在想來(lái)沒(méi)有什么難度苞冯。
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差不多侧巨，是他的一個(gè)子問(wèn)題舅锄。
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
這個(gè)做法比之前的做法更高效，可以保證 O(n) 的復(fù)雜度
Anyway, Good luck, Richardo! -- 10/15/2016
