You’re helping a group of ethnographers analyze some oral history data they’ve collected by interviewing members of a village to learn about the lives of people who’ve lived there over the past two hundred years. From these interviews, they’ve learned about a set of n people (all of them now deceased), whom we’ll denote P1, P2, . . . , Pn. They’ve also collected facts about when these people lived relative to one another. Each fact has one of the following two forms: • For some i and j, person Pi died before person Pj was born; or • for some i and j, the life spans of Pi and Pj overlapped at least partially. Naturally, they’re not sure that all these facts are correct; memories are not so good, and a lot of this was passed down by word of mouth. So what they’d like you to determine is whether the data they’ve collected is at least internally consistent, in the sense that there could have existed a set of people for which all the facts they’ve learned simultaneously hold. Give an efficient algorithm to do this: either it should produce proposed dates of birth and death for each of the n people so that all the facts hold true, or it should report (correctly) that no such dates can exist–that is, the facts collected by the ethnographers are not internally consistent. Assume there are n people and m facts, your algorithm should run in O(n + m) time.
You’re helping a group of ethnographers analyze some oral history data they’ve collected by interviewing members of a village to learn about the lives of people who’ve lived there over the past two hundred
years.
From these interviews, they’ve learned about a set of n people (all of them now deceased), whom we’ll
denote P1, P2, . . . , Pn. They’ve also collected facts about when these people lived relative to one another.
Each fact has one of the following two forms:
• For some i and j, person Pi died before person Pj was born; or
• for some i and j, the life spans of Pi and Pj overlapped at least partially.
Naturally, they’re not sure that all these facts are correct; memories are not so good, and a lot of this was
passed down by word of mouth. So what they’d like you to determine is whether the data they’ve collected
is at least internally consistent, in the sense that there could have existed a set of people for which all the
facts they’ve learned simultaneously hold.
Give an efficient
the n people so that all the facts hold true, or it should report (correctly) that no such dates can exist–that
is, the facts collected by the ethnographers are not internally consistent. Assume there are n people and m
facts, your algorithm should run in O(n + m) time.
One possible solution for this problem is to use topological sorting, which is a well-known algorithm for directed acyclic graphs (DAGs). The idea is to construct a DAG where the nodes represent the people and the edges represent the temporal relationships between them (death before birth or overlapping life spans). If the DAG has a topological ordering, then the data is internally consistent, and we can compute birth and death dates for each person by traversing the DAG in topological order. Otherwise, the data is not internally consistent, and no birth and death dates can exist.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
