## Saturday, December 19, 2015

### The Fake Geek's blog: Find Range

The Fake Geek's blog: Find Range
Given a list of tuples representing intervals, return the range these intervals
covered.
e.g:
[(1,3), (2,5),(8,9)] should return 5
Click here for original question.
I am not a big fan to use fancy containers for problems like this. To me, the primary goal is to reduce time complexity to <= O(n) if possible and maintain constant space complexity. The only reason to use containers is to reduce the time complexity, which is at the expense of space complexity.

Here is an O(n) solution with nothing, just a single loop.
`public` `class` `FindRange {`
` ``public` `int` `findRange (ArrayList<interval> intervals) {`
`  ``if` `(intervals == ``null``)`
`   ``throw` `new` `NullPointerException();`
`  ``if` `(intervals.size() == 0)`
`   ``return` `0;`
`  ``Collections.sort(intervals, ``new` `IntervalComparator());`
`  ``int` `min_start = intervals.``get``(0).start;`
`  ``int` `max_end = intervals.``get``(0).end;`
`  ``int` `range = 0;`
`  ``int` `index = 1;`
`  ``while` `(index <= intervals.size()) {`
`   ``if` `(index == intervals.size()) {`
`    ``range += (max_end - min_start);`
`    ``break``;`
`   ``}`
`   ``if` `(intervals.``get``(index).start <= max_end) {`
`    ``max_end = Math.max(max_end, intervals.``get``(index).end);`
`    ``index++;`
`    ``continue``;`
`   ``}`
`   ``range += (max_end - min_start);`
`   ``min_start = intervals.``get``(index).start;`
`   ``max_end = intervals.``get``(index).end;`
`   ``//index++;`
`  ``}`
`  ``return` `range;`
`  `
` ``}`
` `
` ``private` `class` `IntervalComparator implements Comparator<interval> {`
`  ``public` `int` `compare(Interval a, Interval b) {`
`   ``return` `a.start - b.start;`
`  ``}`
` ``}`
`}`
`public` `class` `Interval {`
`  ``int` `start;`
`  ``int` `end;`
` ``public` `Interval() {`
`  ``this``.start = Integer.MIN_VALUE;`
`  ``this``.end = Integer.MAX_VALUE;`
` ``}`
` ``public` `Interval(``int` `start, ``int` `end) {`
`  ``this``.start = start;`
`  ``this``.end = end;`
`  ``if` `(!isValid()) `
`   ``throw` `new` `IllegalArgumentException(``"invalid input!"``);`
` ``}`
` ``private` `boolean isValid() {`
`  ``return` `start <= end;`
` ``}`
`}`
http://www.careercup.com/question?id=4695029784248320
``````public static int findRange(ArrayList<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.start > o2.start) {
return 1;
} else if (o1.start > o2.start) {
return -1;
} else if (o1.end > o2.end){
return 1;
} else if (o1.end > o2.end) {
return -1;
} else {
return 0;
}
}
});

int range = 0;
int s = 0;
int i = 0;
while (i < intervals.size()) {
int j = i + 1;
int e = intervals.get(i).end;
while (j < intervals.size() && e >= intervals.get(j).start) {
e = Math.max(e, intervals.get(j).end);
j++;

}
range += e - intervals.get(s).start;
i = j;
s = j;
}
return range;
}``````