# 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:

$$$$A = B ... < = < = ... < E < A \\ A < B ... < = < = ... = E < A \\ A < B ... < = < = ... < E < A \\ A < B ... < = < = ... < E = A$$$$ 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 < d_A$$.
• If person $$A$$ died before person $$B$$ was born, then $$d_A < b_B$$.
• 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.