Interval Graph Check

Problem

Decide whether a graph is exactly the intersection graph of a given set of closed intervals.

Two nodes must be adjacent exactly when their intervals overlap (sharing an endpoint counts). Return a boolean. edges is a list of [u, v] pairs and intervals[i] is [start, end] for node i.

Hint

Interval graphs are chordal, but this check goes straight at the overlap definition.

Test cases

case 1

in: [3,[[0,1],[1,2],[0,2]],[[0,2],[1,3],[2,4]]]

expected: true

case 2

in: [3,[],[[0,1],[2,3],[4,5]]]

expected: true

case 3

in: [3,[[0,1],[1,2]],[[0,2],[1,3],[2,4]]]

expected: false

case 4

in: [3,[],[[0,1],[1,2],[2,3]]]

expected: false

Starter codePython

def is_interval_graph(n, edges, intervals):
    # Your code here
    pass

4 test cases · run your code against them in the editor