从Interval 建图

某非一线大厂电面题，
电面的时候我没写出最优解，估计炸了。没签NDA 我来分析一下这道题。
题目比较新，结合了interval和图。
题意是这样的。
给你一堆interval， 每个interval有start time, end time, 和label.
两个interval A， B 之间在如下条件下有edge。

1. B在A的右边而且没有overlap
2. A 和 B之间不能再塞入一个别的interval (这个interval是从输入的list里面的。 如果输入的list里面有这样的interval，则没有edge)
   输出是一个建好的图把所有合法的边都连起来。

面试官浑厚的东欧口音很影响理解题意。
我尝试了两种办法都没有找出最优解。
我先尝用interval的思路试图先sort再从左到右只扫一遍，发现没法弄因为第二个条件有时候会miss掉。
后来又尝试先按第一个条件建图，再DFS删掉2里面不合法的边，被面试官打断了。
他说了一下暴力解，让我写代码了，时间复杂度是 O(N^3).
暴力解是这样对任何两个interval, 先看有没有overlap，再扫描整个list,看能不能塞进第三个interval。
教训应该就是立马写暴力解。写完暴力解再说。

后来面完想了一阵才想到最优解。
最优解应该是这样的。
1。 先把所有interval按start时间排序。
2。从左到右扫
a. 对每一个interval i , 先找到他右边第一个不和它overalp的interval. (可以用binary search来优化)
b. 从第一个non overlap的interval开始往右扫，保留并一直新一个当前最小的end time，当扫到某一个interval的start 时间大于等于这个最小的end time时就停止，之前的所有node都可以和 interval i有边。之后的都没有边。
时间复杂度是 O(N log N + V + E)
where n is the number of spans, V is the vertex number ,E is edge.
In worst case scenario, it is O(n^2).

public class BuildGraph {

    public List<Node> buildGraph(List<Span> spans) {
        // Build all the graph node
        List<Node> graph = new ArrayList<>();
        Collections.sort(spans, new Comparator<Span>() {
            @Override
            public int compare(Span o1, Span o2) {
                return o1.start - o2.start;
            }
        });
       for (Span span : spans) {
            graph.add(new Node(span));
        }
        for (int i = 0; i < graph.size() - 1; i++) {
            Node node = graph.get(i);
            // binary search to find the first node has the starting point >= current node end point.
            int pointer = firstNonOverlap(graph, i);

            // starting from pointer, linear scan with early termination;
            // how many points we need to do depends on the number of edges;
            int curEnd = Integer.MAX_VALUE;
            while (pointer < graph.size()) {
                Node curNode = graph.get(pointer);
                if (curNode.span.start >= curEnd) break; // early termination
                else {
                    node.connectTo(curNode);
                    curEnd = Math.min(curEnd, curNode.span.end); // update the min ending position.
                }
                pointer++;
            }
        }
        return graph;
    }
    // binary search to find the first Node that non overlap with nodes at index i;
    private int firstNonOverlap(List<Node> graph, int i) {
        int end = graph.get(i).span.end;
        int l = i + 1, r = graph.size() - 1;

        while (l < r) {
            int m = l + (r - l) / 2;
            if (graph.get(m).span.start >= end) r = m;
            else l = m + 1;
        }
        if (graph.get(r).span.start < end) {
            return r + 1;
        } else return r;

    }

    class Node {
        Span span;
        Set<Node> children;

        void connectTo(Node that) {
            this.children.add(that);
        }

    public Node(Span span) {
        this.span = span;
        children = new HashSet<>();
    }
}
    class Span {
        String label;
        int start;
        int end;

        public Span(String label, int start, int end) {
            this.label = label;
            this.start = start;
            this.end = end;
        }
    }
}