Intersection of the interval set

Question

Recently I had an interview where it was asked:

Given a list of people with their birth and end years find the year with the most number of people alive.

I implemented in Java and was trying to find the optimal solution. I am sure there might be some data structure which will be optimal to use in this scenario.

static class Person {
    int born;
    int died;

    Person(int born, int died) {
        this.born = born;
        this.died = died;
    }
}

/*
 * (1920, 1939), 
 * (1911, 1944), 
 * (1920, 1955), 
 * (1938, 1939),
 * (1920, 1939),
 * (1911, 1944), 
 * (1920, 1955), 
 * (1938, 1939), 
 * (1937, 1940)
 * 
 */

public static void main(String[] args) {
    List<Person> people = new ArrayList<>();
    people.add(new Person(1933, 1989));
    people.add(new Person(1920, 1939));
    people.add(new Person(1911, 1944));
    people.add(new Person(1920, 1955));
    people.add(new Person(1938, 1939));
    people.add(new Person(1920, 1939));
    people.add(new Person(1911, 1944));
    people.add(new Person(1920, 1955));
    people.add(new Person(1938, 1939));
    people.add(new Person(1937, 1940));
    System.out.println(solution1(people));

}

public static int solution1(List<Person> people) {
    HashMap<Integer, Integer> peopleMap = new HashMap<>();
    int maxCount = 0;
    int year = 0;
    for (Person p : people) {
        for (int i = p.born; i <= p.died; i++) {
            Integer value = peopleMap.get(i);
            if (value == null) {
                peopleMap.put(i, 1);
            } else {
                value++;
                if (maxCount < value) {
                    maxCount = value;
                    year = i;
                }
                peopleMap.put(i, value);
            }
        }
    }
    return year;
}

Answer 1

HashMap is overkill here.

Depending on the constraints of the problem (mainly the minimum and maximum allowable years), you could simply use an array instead of a HashMap.

Sure HashMaps have a O(1) complexity, but nothing is going to beat just indexing an array.

Better algorithm

Coming up with a better algorithm is very tricky.

Your solution is O(NL) where N is the number of people and L is the average lifetime. But keep in mind that L is practically a constant, so it does not really matter that much.

You could most certainly come up with a O(NlogN) solution, based on creating a sorted list of relevant dates. This would outperform your current solution for small values of N, but better performance at the low end is rarely useful (it can be, but that's the exception, not the rule).

Edit Thinking about this, I suspect that's the "trick" part of that interview question. Overlapping intervals is a classic interview problem. However, making the intervals happen on a fully discretized space makes the hashmap solution viable, whereas it can't be used when dealing with "traditional" float-bound intervals.

Answer 2

Nothing wrong with using the HashMap, but…

… all you actually need to store is the overall change for each year. Not even total births or deaths, just the total change. You can iterate at the end, and (keeping a high water mark) to find the maximum you only need to check when your change for the year is positive.

Things that might help

• Sort by birth, and keep a priority queue of deaths.
• Separate the birth and death, sort both lists.

Plenty wrong with the question, though

(the interviewer’s, not your posting here).

• Should changes be considered to happen at the start of the year?
• The end?
• When do you measure?
• Is it the average number for the year, or the maximum possible? Do any of the births happen before any of the deaths?

.. and so on. The problem is a little under-specified.

Answer 3

This problem fits as a temporal problem that requires you to find overlaps between date ranges. SQL is optimized for such problems. But I'm sure it can be done without too much performance loss in managed code.

Should your algorithm take each year as its base unit or just take into account the relevant date time ranges?

I would favour the latter (specially in the OP's problem), unless

• there are short date ranges and many overlaps
• there are a huge amount of overlaps

What can be a good algorithm for finding the hot spot?

In chronological order, I would

• find relevant date ranges: add all start and end dates in a bag, remove duplicates, order by ascending date, pair up adjacent dates as a relevant date range.
• determine overlaps: for each relevant date range, store the number of people that have lived in this period
• take date range with highest amount of overlaps

Note that since this is not SQL, but rather managed code, an inline algorithm can be used that only keeps track of the date range that has currently (in the algorithm) the highest amount of overlaps.