Пересечение интервалом


Недавно у меня было интервью, где его спросили:
Приведенный список людей с их рождения и конца года найти год с наибольшим количеством живых людей. Я реализована в Java и пытаюсь найти оптимальное решение. Я уверен, что там может быть какая-то структура данных, которая будет оптимальной для использования в данной ситуации.

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;
}


Комментарии
2 ответа

HashMap является излишним здесь.

В зависимости от ограничений задачи (в основном минимальное и максимальное допустимое лет), вы могли бы просто использовать массив вместо этого HashMap.

Конечно всех HashMap есть сложностью O(1), но ничего не собирается бить просто индексация массива.

Лучше алгоритм

Придумать более эффективный алгоритм очень сложно.

Ваше решение O(NL) где N количество людей и L это средняя продолжительность жизни. Но имейте в виду, что L практически постоянный, так что это действительно не имеет значения, что много.

Вы наверняка могли бы придумать O(NlogN) решение, основанное на создании отсортированный список соответствующих дат. Это позволит превзойти вашего текущего решения для малых значений Nно улучшения производительности на нижнем конце используется редко (это может быть, но это исключение, а не правило).

Редактировать думая об этом, я подозреваю, что это "фишка" часть этого интервью вопрос. Перекрывающиеся интервалы-это классическая проблема интервью. Однако, делая интервалы происходить на полностью дискретизированное пространство делает решение этого HashMap жизнеспособными, в то время как он не может быть использован при работе с "традиционными" поплавок-граница интервалов.

0
ответ дан 6 апреля 2018 в 04:04 Источник Поделиться

Ничего плохого в использовании в HashMap, но...

... все, что вам на самом деле нужно хранить в целом для каждого года. Даже не общее число рождений или смертей, только общее изменение. Вы можете перебирать в конце, и (держать высокий водяной знак), чтобы найти максимальное нужно только проверить, когда ваши изменения за год является положительным.

Вещи, которые могут помочь


  • Сортировать по рождению, и сохранить приоритет в очереди смертей.

  • Отдельная рождения и смерти, отсортировать оба списка.

Много плохого, но все-таки

(интервьюер, а не ваш постинг здесь).


  • Изменения должны быть рассмотрены, произошло в начале года?

  • Конец?

  • Когда вы измеряете?

  • Это среднее число за год, или максимально возможная? Выполните любое из рождения произошло до смерти?

.. и так далее. Проблему немного под-указанным.

0
ответ дан 7 апреля 2018 в 12:04 Источник Поделиться