JavaScript: Find the point where maximum intervals overlap

Question

I need help on my homework, I got this question and don't know how to find the answer:

Consider a group of retired people, where any person start to work in a year X and got retired in a year Y. Create a function that recieves an a array following the structure: [[x1,y1],[x2,y2],...[xn,yn]] and calculate which year(s) has most people working.

Consider:

• The X values as the year that the person starts working (x>0, x<y);
• The Y values as the year that the person gets retired (y>0);
• The beginning year must be considered as a worked year;
• The retired year must be considered as a worked year.

Example: Input [[1960,2005],[1945,2008],[1938,1999],...]

I tried to get the lowest and highest years to compare and goes year by year counting how many people was working but it didn't work out.

EDIT: I managed to transform the array into one and sorted all the worked years. Now i need to manage how to find what person worked each year. The code that i developed is following:

var variety = [[2000,2008],[2003,2009],[2001,2012],[2004,2020],[2003,2021],[1998,2015]], year = [], anos2 = 0, k=0, minYear=0, maxYear=0
function getyear(people){
    for(var lin = 0; lin < people.length; lin++){ //Esse for é para transformar a matriz em um único vetor dinamicamente
        for(var col = 0; col < people.length-(people.length-2); col++){
            year[k] = people[lin][col]
            k++
        }
    }
    year.sort(compareNumbers) //Ordena o vetor dos anos trabalhados
    console.log(year)
    console.log(people)

}
function compareNumbers(a,b){
    return a -b
}
getyear(variety)

Answer 1

From your question, it seem you are having a hard time on how to approach the problem and not on how to code it. I hope the following insight might help you.

What about creating an array of integer from minYear to maxYear with initial value of 0. Each time you have a user that started working at year X and retired at year Y, you simply increment the number in the array for each of those year.

Thus a person working from 1960 to 2015 would have the value 1 in the array for the value 1960 up to 2015. Repeat for every users.

Afterward, you can loop the array to find the highest value and lowest value within the array. This also simplify the logic as there could be multiple maximum peak and multiple minimum peak.

There could be also an alternative where you do not allocate as much memory by not creating any array and looping for every years from minYear to maxYear. For each of those year, you will need to loop for all employee to count how many were working for that said year. Save the first year as min and max value and for every other year you go by, if the value is higher than highest or lower than lowest, simply update it and use that as the new peak value. This use least memory, but would use more CPU.

There are always some alternative method that enable better CPU and memory efficiency. But for a beginner approach, both of these method would be acceptable.

Answer 2

Function:

const getCounts = (arr = []) =>
{
    const years = {};
    let x, y, year;
    arr.forEach( item => {
        x = item[0];
        y = item[1];
        for ( year = x ; year <= y ; ++year )
        {
            if(years[year] === undefined)
            {
                years[year] = 0;
            }
            years[year]++;
        }
    });
    return years;
}

Sorting:

const output = getCounts([[1960,2005],[1945,2008],[1938,1999]]);

console.log( Object.entries(output).sort( (a,b) => b[1] - a[1] ) );

Answer 3

The following approach utilizes the algorithm described in this article. Unlike previous answers, this does not explode all ranges into years unnecessarily, nor does it iterate over every year in every range. Rather it returns the maximum number of people worked at the same time, and an array of ranges during which that number of people were employed. It is trivial to convert the array of ranges to an array of years, if required.

const f = input=>Object.entries(
  // sum up entries/exits by year
  input.reduce(
    (a,[s,e])=>(
      a[s] = (a[s]||0)+1,
      a[e] = (a[e]||0)-1,
      a
    ),{}
  ))
  // convert years back to numbers
  .map(([s,e])=>[1*s,e])
  // sort ascending by year
  .sort(([r],[l])=>r-l)
  .reduce((a,[y,c])=>{
    a.count += c;
    switch (Math
      .sign(a.count - a.r.max)) {
    case 1: // count > max
      // set max; clear ranges
      a.r = {max:a.count,ranges:[]};
      // fall through
    case 0: // count === 0
      // open new range
      a.r.ranges.push([y]);
      break;
    case -1: // count < max
      // close range, if open
      a.r.ranges.push([
        ...a.r.ranges.pop(), y
      ].slice(0,2));
      break;
    }
    return a;
  },{ // initial values
    count:0,
    r:{max:0,ranges:[]}
  })
  // return results object
  .r;

For example:

const input = [
  [1960,2005],
  [1945,2008],
  [1938,1999]
];

console.log(f(input1));

This will result in:

{ max: 3, ranges: [ [ 1960, 1999 ] ] }

Indicating that the maximum number of workers, concurrently employed was 3, and that 3 workers were employed concurrently during the years of 1960 through 1999, inclusive.

In a more complex example below, I used small integers for years, for brevity:

const input = [
  [1,9],
  [1,2],
  [8,9],
  [2,3],
  [5,7],
  [7,9],
  [5,6],
  [8,9],
  [5,9],
  [4,8],
  [1,3]
];

console.log(f(input));

The result is:

{ max: 5, ranges: [ [ 5, 6 ], [ 8, 9 ] ] }

Indicating that the maximum number of workers at the same time was 5, and that 5 workers were concurrently employed in two non-overlapping intervals: years 5 through 6 and 8 through 9.

The following function can be used to explode an array of ranges into a flat array of years, if required:

const explode = ranges=>
  [].concat(
    ...ranges.map(([s,e])=>Array.from(
      {length:e-s+1},(_,i)=>i+s
    ))
  );

For example:

const input = [
  [1,5],
  [6,7],
  [9,9]
];
  
console.log(explode(input));

Will result in the following:

[ 1, 2, 3, 4, 5, 6, 7, 9 ]

Answer 4

Perhaps you can do like this;

var years  = [[2000,2008],[2003,2009],[2001,2012],[2004,2020],[2003,2021],[1998,2015]];
    result = years.map(ys => Array.from({length:ys[1]-ys[0]+1}, (_,i) => ys[0]+i))
                  .reduce((p,c) => p.filter(e => c.includes(e)));

console.log(result);

The

years.map(ys => Array.from({length:ys[1]-ys[0]+1}, (_,i) => ys[0]+i))

part turns your [[2000,2008],[2003,2009],[2001,2012],[2004,2020],[2003,2021],[1998,2015]] array into

[[2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008]
,[2003, 2004, 2005, 2006, 2007, 2008, 2009]
,[2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012]
,[2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020]
,[2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021]
,[1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015]
]

and the .reduce((p,c) => p.filter(e => c.includes(e))) part just reduces by intersecting.

This is just a naive but intuitive way. Developing from the idea you should be able to do this by a single .reduce() stage. So that it is still a homework.

So the above solution is ok for the given data set however there is a rightful comment. So i switch to an efficient code here. It returns you an object where the properties are years those are subject to people working and values are the the headcount per year.

var years = [[2000,2008],[2003,2009],[2001,2012],[2004,2020],[2003,2021],[1998,2015]];
    result = years.reduce(function(r,ys) {
                            for (var y = ys[0]; y <= ys[1]; y++){
                              r[y] = r[y] ? r[y]+1 : 1
                            }
                            return r;
                          },{});
console.log(result);

.as-console-wrapper {
max-height: 100% !important
}