leetcode/algorithms/MergeIntervals.js at master · zzxboy1/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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * Definition for an interval.
 * function Interval(start, end) {
 *     this.start = start;
 *     this.end = end;
 * }
 */
/**
 * @param {Interval[]} intervals
 * @return {Interval[]}
 */
var merge = function(intervals) {
    if (intervals.length === 0) {
        return intervals;
    }
    let result = [intervals[0]];
    for (let i = 1; i < intervals.length; i++) {
        let obj = [];  // [{index: x, pos: 'right' or 'left'},{index: x, pos: 'right' or 'left'}]
        for (let j = 0; j < result.length; j++) {
            if (j === result.length -1 && intervals[i].start > result[j].end) {
                result.push(intervals[i]);
                break;
            }
            if (j === 0 && intervals[i].end < result[j].start) {
                result.unshift(intervals[i]);
                break;
            }
            if (intervals[i].start <= result[j].end && intervals[i].start >= result[j].start) {
                obj[0] = { index: j, pos: 'mid'};
            } else if (intervals[i].start <= result[j].start && ( j ===0 || intervals[i].start > result[j - 1].end)) {
                obj[0] = { index: j, pos: 'left'};
            }
            if (intervals[i].end >= result[j].end && (j === result.length -1 || intervals[i].end < result[j + 1].start)) {
                obj[1] = { index: j, pos: 'right'};
            } else if (intervals[i].end >= result[j].start && intervals[i].end <= result[j].end) {
                obj[1] = { index: j, pos: 'mid'};
            }
            if (obj[1] && obj[0]) {
                break;
            }
        }
        if(!obj[1] || !obj[0] ) {
            continue;
        }
        let start = obj[0].index,
            end = obj[1].index;
        if (obj[0].pos === 'mid') {
            if (obj[1].pos === 'mid') {
                if (obj[0].index === obj[1].index) {
                    continue;
                } else {
                    const newItv = new Interval(result[start].start, result[end].end);
                    result.splice(start, end - start + 1, newItv);
                }
            } else if (obj[1].pos === 'right') {
                const newItv = new Interval(result[start].start, intervals[i].end);
                result.splice(start, end - start + 1, newItv);
            }
        } else if (obj[0].pos === 'left') {
            if (obj[1].pos === 'mid') {
                const newItv = new Interval(intervals[i].start, result[end].end);
                result.splice(start, end - start + 1, newItv);
            } else if(obj[1].pos === 'right') {
                const newItv = new Interval(intervals[i].start, intervals[i].end);
                if (obj[0].index > obj[1].index) {
                    result.splice(start, 0, newItv);
                } else {
                    result.splice(start, end - start + 1, newItv);
                }
            }
        }
    }
    return result;
};