Most Living People

June 5, 2015

We have today an exercise inspired by those “programming challenge” websites where you upload code and an automated judge tells if you pass or fail and how your time compares to other programmers. I haven’t seen this particular problem at one of those sites, but it feels like something they would do; this would also make a good interview question:

You are given a list of people’s lifespans with birth and death years; for instance, a person lived from 1924 to 1991. Some people have only a birth year because they are still living. You are to find the year in which the most people of a set of people were alive.

Input: A number n on a line by itself indicating the number of input cases, followed by n sets of lines containing a number m indicatingthe number of people in this particular input case, followed by m lines indicating birth and, possibly, death years.

Output: For each input case, the year (or years) in which the most people were alive.

Example: For the input:

```2
3
1910 1948
1948 2011
1927 1995
3
1910 1948
1927 1995
1945```

You should produce the following output:

```1948
1945 1946 1947 1948```

Your task is to write the indicated program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

8 Responses to “Most Living People”

1. In perl – this is what perl was written for!

my \$Y = 2015;
my \$cases = ;
foreach my \$case ( 1..\$cases ) {
my \$rows = ;
my %years;
foreach my \$row ( 1..\$rows ) {
\$_ = ;
my(\$s,\$e) = split;
\$years{\$_}++ foreach \$s..(\$e||\$Y);
}
my \$max = 0;
foreach (values %years) {
\$max = \$_ if \$max < \$_;
}
printf "@{[ sort grep {\$years{\$_}==\$max} keys %years ]}\n",
}

2. Priyank said

I was wondering if there is a better data structure/algorithm to solve this ?

Intersection of intervals and maintaining a count of intersection ?

3. haari said
```public class LifeSpan {

public static void main(String[] args) throws NumberFormatException,
IOException {
LifeSpan ls = new LifeSpan();
List<List<Integer>> listOfAllYears = new ArrayList<List<Integer>>();

Scanner scanner = new Scanner(System.in);
System.out.println("Enter the Number of cases to be examined");
int n = scanner.nextInt();

for (int i = 1; i <= n; i++) {

System.out.println("Enter Number of People");
Scanner s = new Scanner(System.in);

List<List<Integer>> list = new ArrayList<List<Integer>>();

for (int j = 0; j < numberOfLinesToRead; j++) {
result[j] = s.nextLine();
}

for (int a = 0; a < result.length; a++) {
ls.calCommonYearString(result[a], list);
}
}

for (List<Integer> l : listOfAllYears) {
l.toArray();
for (Integer h : l) {
System.out.print(h + " ");
}
System.out.println();
}
}

private void calCommonYearString(String string, List<List<Integer>> list2) {
List<String> list = new ArrayList<String>();
StringTokenizer str = new StringTokenizer(string, " ");
if (str.countTokens() < 2) {
Calendar now = Calendar.getInstance();
String currentYear = String.valueOf(now.get(Calendar.YEAR));
} else {
while (str.hasMoreTokens()) {
}
}
calCommonYear(list, list2);
}

private void calCommonYear(List<String> list, List<List<Integer>> list2) {
int a = Integer.parseInt((String) list.get(0));
int b = Integer.parseInt((String) list.get(1));
List<Integer> every = new ArrayList<Integer>();
for (int i = a; i <= b; i++) {
}
}

private void setToReturn(List<List<Integer>> list, int numberOfLinesToRead,
List<List<Integer>> listOfAllYears) {
List<Integer> temp = null;
for (int i = 0; i <= numberOfLinesToRead - 1; i++) {
if (i == 0) {
temp = list.get(i);
}
temp.retainAll(list.get(i++));
i--;
}
}
}
```
4. haari said

The above code is written in java and assuming all the validations are true

5. Prabu said

Haari, I tried a solution with set too. The problem is when there is a range which doesn’t overlap at all (someone noncontemporary).
Try this dataset – there wont be any output.
1(# of cases)
3(# of entries)
2010
1910 1948
1927 1995

Though expected output is 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948.

6. haari said

Prabhu, go through the task once more. The task to print a common year lived by all the people. In your dataset, if you give 2010, it won’t be a common year for all the 3 people since other people died in 1948 and 1995 so there wont be any output.

7. H. F. said

Consider an inverse problem: you are given a list of birth years and a list of death years for a group of people. The same birth (or death) year may be listed for multiple times if there are more than one birth (or death) in that year. However, the two lists are separate and no names are attached to each year. Please estimate the numbers of years that these people have lived.

8. Mike said
```from collections import Counter
from datetime import date

def mostliving(line):
thisyear = date.today().year
for case in range(int(next(line))):
pop = Counter()
for person in range(int(next(line))):
birth, *tail = [int(s) for s in next(line).split()]
death = tail[0] if tail else thisyear
pop.update(range(birth, death+1))

maxpop = max(pop.values())
print(*[y for y,p in sorted(pop.items()) if p == maxpop])

# test
data = """\
2
3
1910 1948
1948 2011
1927 1995
3
1910 1948
1927 1995
1945
"""

mostliving(io.StringIO(data))

```