Problem -

Given a list of people with each person’s birth year and death year, find the year with the highest population.

Solution -

I am writing about this problem , becuase it has a very sweet optimization which can easily get missed f we do not give it a thought.

I am skipping the brute force way of solving it which is not the best solution. An optmized solution is record popluation for each year in a secndary data structue. Lets take a hashmap for the same. Iterate through the list of people and increment the count all the years he is alive abd decrement for the years he dies.

Once you have traversed all the people, pick up any year with maximum value.

Code in scala looks like following…

 1 import scala.collection.mutable.Map
  3 object MaxPopulation {
  4   case class years(birth: Int, death: Int)
  5   val input: Seq[years] = Seq(years(1962, 2015), years(1967, 2005), years(1912, 1975) , years(1902, 1999), years(1942, 2000))
  7   def main(args: Array[String]): Unit = {
  8     val yearMap = Map.empty[Int, Int].withDefaultValue(0)
 10     input foreach { person =>
 11       for {
 12         alive <- person.birth until person.death
 13       } yearMap(alive) += 1
 16        yearMap(person.death) -= 1
 17     }
 18     val max = yearMap.maxBy {case (key, value) => value}
 19     println(max)
 20   }
 21 }


If no one is born in a year, we do not really need to track a year. in other words dont track the year with just deaths, population can not be maximum in them.

so line 16 becomes this

if (yearMap(person.death) > 0) yearMap(person.death) -= 1