Archaeological Consistency: Graph Problem

So, I have an issue with the following problem (CS 161 Stanford 2013, Problem Set 2):

Suppose that you have found a collection of historical records indicating the relative order in
which various people lived and died. Each record tells you one of the following:

• Person A and person B were alive at the same time.

• Person A died before person B was born.

Your task is to determine whether the historical records are consistent; that is, whether it was actually possible for all of these people to have lived and died in such a way that all of your records are accurate. Suppose that your records involve n total people and you have m records relating their lifespans.

I need to design an O(m + n)-time algorithm that determines whether or not the records are consistent with one another. The problem would be very simple if we only have statements that a person died before another person was born (we would simply need to look for a directed loop), however, the presence of statements that some people lived at the same time makes it more complex. I tried to understand what kinds of "inconsistencies" we can have, and it seems that there can be inconsistencies of the following four kinds ($A = B$ means that $A$ and $B$ lived at the same time, $A < B$ means that $A$ died before $B$ was born:

\begin{equation}
A = B ... < = < = ... < E < A \\
A < B ... < = < = ... = E < A \\
A < B ... < = < = ... < E < A \\
A < B ... < = < = ... < E = A
\end{equation}
where $... < = < = ...$ represents some arbitrary sequence of people born after / living at the same time as the previous person. I also note that if we have two "equality signs" in a sequence after each other, this sequence cannot be a contradiction in and of itself. But I cannot see how to proceed from here.

Denote the time of birth of person $A$ by $b_A$, and their time of death by $d_A$, and suppose for simplicity that all of these times are different. We know that:

• For every person $A$, $b_A

• If person $A$ died before person $B$ was born, then $d_A

• If person $A$ and person $B$ were alive at the same time then $d_A > b_B$ and $d_B > b_A$, and these conditions characterize this property.

You take it from here.

StackExchange Computer Science Q#147788, answer score: 5