# Defeat 95% Java, AC new Hash solution (no-sort!!!)

• using hash array to record the entry status:
use -1, 0, 1, 2 to mark the status:
0: not in any intervals
-1: in the interval that end=start, e.g. [1,1]
1: the entries (except for end entry) of any interval that end!=start
e.g. for [1,3]:
hash[1] and hash[2] are in status 1.
2: the end of any interval that end!=start
e.g. for [1,3]:
hash[3] is in status 2.

Caution:
priority: 1>2>-1>0.

public class Solution {
public List<Interval> merge(List<Interval> intervals) {
int MAX = -1;
for(int i=0; i<intervals.size(); i++) { // get maxmium entry
if(intervals.get(i).end > MAX) MAX = intervals.get(i).end;
}
//using hash array
int[] hash = new int[MAX+2];
for(int i=0; i<intervals.size(); i++) {
if(intervals.get(i).start == intervals.get(i).end) {
if(hash[intervals.get(i).start] == 0) //do not disturb other intervals
hash[intervals.get(i).start] = -1;
}
else {
for(int j=intervals.get(i).start; j<intervals.get(i).end; j++) {
//from start to end
hash[j] = 1;
}
//we have to make sure [1,3] [4,6] can not be merged
// we have to also make sure this will not end up the previous continuous intervals
if(hash[intervals.get(i).end] != 1)
hash[intervals.get(i).end] = 2; //end sign
}
}
//traverse to get merged section
List<Interval> result = new ArrayList<Interval>();
int s = -1;
for(int i=0; i<=MAX+1; i++) {
if(hash[i] == -1) { // self-interval
}
else if(hash[i] == 1 && s == -1) { // new interval
s = i;
}
else if(hash[i] == 2 && s!=-1) { // interval is end