Find an algorithm for counting the number of multiple overlapping intervals, as well as the duration of such intervals?

Question

JavaScript

Assignment:
Petya decided to find out when it is most profitable for a programmer to look for a job on hh.ru. Of course, when the most open vacancies.

He uploaded the opening and closing times of all eligible vacancies for 2019 to a text file.

Now you need to determine the period of time when there were the most open vacancies.

We believe that:

- start and end times are always present;
- the start time is always less than or equal to the end time;
- start and end times are included in the interval.

Input data
The input information comes from the standard input, in the first line comes 1 number - the number of vacancies. Each of the following lines contains information about the vacancy in the form of two numbers - the start and end times, they are separated by a space. The time is given in seconds ( https://ru.wikipedia.org/wiki/Unix-time ). Incorrect input data is not received, additional checks are not required.

Output
As an answer, two numbers must be output to the standard output separated by a space: the number of intervals found and the sum of the duration of the intervals in seconds (the beginning and ending seconds must be included in the interval).

Example 1
Input:

1
1595862781 1595862785
Output: 1 5

Example 2
Input:

2
1595862781 1595862783
1595862782 1595862784
Output: 1 2

Example 3
Input: 2

1595862781
1595862782 1595862783
1595862783 1595862784 The solution does not need to specify a package. To work with standard input in JS, use require('readline'), and to work with standard output, use console.log(String(data)). JS I/O example:

const readline = require('readline');
const rl = readline.createInterface(process.stdin, process.stdout);
rl.on('line', (line) => {
    // Введенная строка в переменной line, тут можно написать решение
    console.log(String(result));
    rl.close();
    return;
}).on('close', () => process.exit(0));

Before submitting your solution, we recommend that you run tests from the Testing section, they will help you catch syntax and runtime errors.

My solution (these tests pass, but give an error in closed internal tests):

const readline = require('readline');
const rl = readline.createInterface(process.stdin, process.stdout);
let lines = [];
rl.on('line', (line) => {
  lines.push(line);
}).on('close', () => {
  function calculateTime(strArr) {
    let vacanciesNum = strArr.shift();
    let vacanciesTime = strArr;
    let intervalFound = [];
    let count = 0;
    vacanciesTime.sort();

    vacanciesTime.reduce((prev, next) => {
      if (prev === next) {
        count++;
      }
    });

    for (let i = 0; i < vacanciesNum; i++) {
      let startTime = +vacanciesTime[i].split(" ")[0];
      let endTime = +vacanciesTime[i].split(" ")[1];
      let intervalFoundI = [];

      for (let j = 0; j < vacanciesNum; j++) {
        if (
          startTime <= +vacanciesTime[j].split(" ")[1] &&
          endTime >= +vacanciesTime[j].split(" ")[0]
        ) {
          intervalFoundI.push(vacanciesTime[j]);
        } // a.start <= b.end AND a.end >= b.start
      }
      intervalFound.push(intervalFoundI);
    } // находим все вхождения интервалов

    intervalFound = intervalFound.filter(
      ((r = {}), (a) => !(r[a] = ++r[a] | 0))
    ); // убираем одинаковые вхождения

    let maxLength = intervalFound.reduce(function (acc, el) {
      return el.length > acc ? el.length : acc;
    }, 0); // считаем максимальную длину массива

    intervalFound = intervalFound.filter((val) => {
      return val.length === maxLength;
    }); // отфильтровываем только максимальные значения

    let totalIntervalLength = intervalFound.reduce(
      (acc, val) => {
        let maxStart = val[0].split(" ")[0];
        let minEnd = val[0].split(" ")[1];

        for (const str of val) {
          if (maxStart < str.split(" ")[0]) {
            maxStart = str.split(" ")[0];
          }
          if (minEnd > str.split(" ")[1]) {
            minEnd = str.split(" ")[1];
          }
        }

        return (acc += minEnd - maxStart + 1);
      },
      0
    ); // Вычисляем общую длину интервала

    return `${
      count + intervalFound.length
    } ${totalIntervalLength}`;
  }
  
  console.log(calculateTime(lines));
  process.exit(0);
});

Answer 1

I'm too lazy to understand your code. Here is the correct solution:
For all intervals, add the pairs {start time, +1} and {end time+1, -1} to the array of points. This is an array of points - the boundaries of vacancies on the time axis (add 1 to the end time, because the last second is included in the interval). Then we sort this array. Now, with one pass, you can select all time intervals from the array and how many vacancies were opened on them.
To do this, start a counter, initially equal to zero, and go through the array, adding the current second value to the counter at the end of the loop .
Before that, if the current point lies to the right of the previous one, then the segment from the previous point to the current one has exactly as many open vacancies as are recorded in the counter.
For simplicity, I advise you to first select all the segments in one cycle and add them to a separate array (again, a pair - the length of the segment, the number of vacancies). Then go through the array (or while folding) to find the maximum number of vacancies. Then go through again and sum up the times for all segments with a given number of vacancies.
You can also look at the previous answer to your fellow student: What is the error in the algorithm for finding the number of intervals?