Timeline based approach O(n logn) time and O(n) space


  • 0
    N
    public class Solution {
    class Node{
        int val;
        int mark;
        Node(int x, int y){
            this.val = x;
            this.mark = y;
        }
    }
    class NodeComparator implements Comparator<Node>{
    	@Override
    	public int compare(Node n1, Node n2) {
    		int val = n1.val - n2.val;
            if(val != 0){
                return val;
            }
            return n2.mark - n1.mark;
    	}
    }
    public List<Interval> merge(List<Interval> intervals) {
        Node[] list = new Node[intervals.size()*2];
        int t = 0;
        for(Interval i : intervals){
            list[t++] = new Node(i.start, 1);
            list[t++] = new Node(i.end, -1);
        }
        Arrays.sort(list, new NodeComparator());
        int start = 0;
        List<Interval> overlap = new ArrayList<>();
        Interval x = null;
        for(Node n : list){
            if(n.mark > 0){
                if(start == 0){
                    x = new Interval();
                    x.start = n.val;
                }
                start++;
            }
            if(n.mark < 0){
                start--;
                if(start == 0){
                    x.end = n.val;
                    overlap.add(x);
                }
            }
        }
        return overlap;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.