Intersection of the interval set 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&lt;Person&gt; people = new ArrayList&lt;&gt;();
    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&lt;Person&gt; people) {
    HashMap&lt;Integer, Integer&gt; peopleMap = new HashMap&lt;&gt;();
    int maxCount = 0;
    int year = 0;
    for (Person p : people) {
        for (int i = p.born; i &lt;= p.died; i++) {
            Integer value = peopleMap.get(i);
            if (value == null) {
                peopleMap.put(i, 1);
            } else {
                value++;
                if (maxCount &lt; value) {
                    maxCount = value;
                    year = i;
                }
                peopleMap.put(i, value);
            }
        }
    }
    return year;
}
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.