6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

You take it from here.

$\endgroup$
2
  • $\begingroup$ Just to be sure, we need to create two vertices per person. Then, create a directed graph based on the above defined relations and check if there exists a cycle or not? Also, a minor comment: shouldn't it be better to say "if and only if" instead of "if, then" in all the above statements. $\endgroup$ Dec 22 '21 at 16:57
  • 2
    $\begingroup$ Sometimes “if” means “iff”. $\endgroup$ Dec 22 '21 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.