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

  • 0
    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 most vacancies are open.

    He dumped the opening and closing times of all eligible jobs for 2019 into 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 time 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
    Input information comes from standard input, the first line contains 1 number - the number of vacancies. Each of the following lines contains information about the vacancy in the form of two numbers - start and end times, separated by a space. The time is set in seconds ( https://ru.wikipedia.org/wiki/Unix-time ). Incorrect input data are not received, additional checks are not required.

    Imprint
    As an answer, two numbers should be printed to standard output separated by a space: the number of found intervals and the sum of the duration of the intervals in seconds (the initial and final seconds must be included in the interval).

    Example 1
    Input data:

    1
    1595862781 1595862785
    Imprint: 1 5

    Example 2
    Input data:

    2
    1595862781 1595862783
    1595862782 1595862784
    Imprint: 1 2

    Example 3
    Input data:

    2
    1595862781 1595862782
    1595862783 1595862784
    Imprint: 2 4

    Notes on the design of the solution
    When submitting solutions in Java, you need to name the executable class Main. The solution does not need to include a package.

    Use require ('readline') to work with standard input in JS, and console.log (String (data)) to work with standard output.

    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 the tests from the Testing section to help catch syntax and runtime errors.

    My solution (these tests pass, but gives 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);
    });
    JavaScript Anonymous, May 11, 2020

  • 1 Answers
  • 0
    I am too lazy to understand your code. Here is the correct solution:



    For all intervals add pairs {start time, +1} and {end time + 1, -1} to the point array. 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, in one pass, you can select from the array all time intervals and how many vacancies were opened for 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 written in the counter.



    For simplicity, I advise you to first select all segments in one cycle and add them into a separate array (again a pair - segment length, number of vacancies). Then go through the array (or during folding) to find the maximum number of vacancies. Then go through one more time 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?
    Anonymous

Your Answer
To place the code, please use CodePen or similar tool. Thanks you!