Year with the most living (given a list of births and deaths)

Question

I am trying to find the year most people are alive, given a list of births and deaths. I am not sure my approach is optimal or if am calculating the time complexity correctly

Break down: I sort the dates O(n log n) I walk the dates in order O(b + n log n)

Hashing the births, because they pivot the shifts between the number of living from those already dead. Since a birth year will be the year in which most people lived.

I am also pushing the deaths into a common array.

I then loop over the deaths O(n^2 + n log n)

grabbing the count of those deceased and subtracting that from those still alive, and resting the array with those still alive on every iteration.

finally, I loop over the hash results to get the highest result. with a final time complexity after dropping all constants

O(n+m) or O(n^2)

const people = [{ birth: 1720, death: 1860 },{ birth: 1720, death: 1860 },{ birth:1803, death: 1809},{ birth: 1730, death: 1810 },{ birth: 1920, death: 1950 },{ birth: 1930, death: 1940 },{ birth: 1940, death: 1990 }, { birth: 1970, death: 2010 }]
function yearMaxAlive(people) {
  people.sort((a, b) => a.birth - b.birth)
  let high = {
      year: 0,
      count: 0
    },
    alive = 0,
    survivors = [];
  for (let [year, count] of Object.entries(people.reduce((deaths => (ledger, year) => {
      if (ledger[year.birth]) {
        alive++
        ledger[year.birth].alive = alive
      } else if (!ledger[year.birth]) {
        if (deaths.length > 0) {
          let deleted = deaths.filter((a, i, aa) => {
            if (a <= year.birth) {
              return true
            } else {
              survivors.push(a)
              return false
            }
          })
          deaths = survivors
          survivors = []
          alive = alive - deleted.length
          alive++
          ledger[year.birth] = {
            alive: alive,
            deaths: deaths
          }
        } else {
          alive++
          ledger[year.birth] = {
            alive: alive,
            deaths: deaths
          }
        }
      }
      deaths.push(year.death)
      return ledger
    })([]), {}))) {
    if (high.count < count.alive) {
      high = {
        year: year,
        count: count.alive
      }
    }
  }
  return high
}

console.log(yearMaxAlive(people))

Answer 1

The optimal algorithm is about O(n) to generate the count changes per year (and optionally get the first and last year), and about O(m) for enumerating them to find the first year with highest count (where m is preferably the number of years from the first to last year).

var people = [{ birth: 1720, death: 1860 },{ birth: 1720, death: 1860 },{ birth:1803, death: 1809},{ birth: 1730, death: 1810 },{ birth: 1920, death: 1950 },{ birth: 1930, death: 1940 },{ birth: 1940, death: 1990 }, { birth: 1970, death: 2010 }];

var counts = people.reduce((a, v) => (a[v.birth] = (a[v.birth] | 0) + 1, 
                                      a[v.death] = (a[v.death] | 0) - 1, a), []);

var maxYear = 0, maxCount = 0, count = 0;
counts.forEach((c, y) => {
  count += c;
  if (maxCount < count) {
    maxCount = count;
    maxYear = y;
  }
});

console.log( maxYear, maxCount );
console.log( { ...counts } );

The above is just a sample, and can be much more efficient with for(;;) loops and starting the second loop from the first year 1720 instead of 0. The count changes can be in either object {} or Array object [] as long as they are enumerated in order from low to high.