What is the error in the algorithm for finding the number of intervals?

Question

Java

Comrades, experts, please poke into the algorithm error:

Condition:

We believe that:

- the 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.

Specifications Input
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 should 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 Example data : 1
5

example _ _ _ _

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Main {

    public static void main(String[] args) throws IOException {
        // write your code here
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            String str = "";
            int count = 0;
            ArrayList<MyClass> arrayList = new ArrayList<>();
            if ((str = reader.readLine()) != null) {
                count = Integer.parseInt(str.trim());
            }

            for (int i = 0; i < count; i++) {
                str = reader.readLine();
                arrayList.add(new MyClass(Long.parseLong(str.split(" ")[0]), 1)); //начало
                arrayList.add(new MyClass(Long.parseLong(str.split(" ")[1])+1, -1));  //конец
            }
            if (count != 0) {
                findPair(arrayList);

            } else {
                System.out.println(0 + " " + 0);
            }
        }
    }

    private static void findPair(ArrayList<MyClass> arrayList) {
        Collections.sort(arrayList, Comparator.comparingLong(MyClass::getX));

        int maxVac = 0;
        int maxVacNum = 0;
        int resNum = 0;
        long resTime = 0;
        long maxVacTime = 0;
        long maxStart = 0;
        int cnt = 0;
        for (int j =0; j<arrayList.size(); j++) {
            if (arrayList.get(j).getY() > 0) {
                cnt +=arrayList.get(j).getY();
                if (cnt > maxVac) {
                    maxVac = cnt;
                    maxVacNum = 1;
                    maxStart = arrayList.get(j).getX();
                    maxVacTime = 0;
                } else if (cnt == maxVac) {
                    maxVacNum += 1;
                    maxStart = (arrayList.get(j).getX());

                }
            } else {
                if (cnt == maxVac) {
                    maxVacTime += (arrayList.get(j).getX() - maxStart);
                }
                cnt +=arrayList.get(j).getY();


            }
            if (maxVacNum >= resNum && maxVacTime > resTime) {
                resNum = maxVacNum;
                resTime = maxVacTime;
            }
        }
        System.out.println(resNum + " " + resTime);


    }

    public static class MyClass {
        long x;
        int y;

        public MyClass(long x, int y) {
            this.x = x;
            this.y = y;
        }

        public long getX() {
            return x;
        }

        public int getY() {
            return y;
        }

    }
}

tests pass, everything seems to count smoothly, but the validator is smarter than my tests

Answer 1

You correctly decided to sort the ends of the segments, but the heuristic with +-1 as the second sort parameter does not work for you. It looks like there is an error there. Try the test, "6 100 102 100 102 100 102 102 104 102 104 102 104". The answer should be - 1 segment of length 1 (there are 6 vacancies in the 102nd second). Another interesting test is "6 100 102 100 102 100 102 103 104 103 104 103 104". Here the answer is 1 5 (3 vacancies).
The problem is that this sorting approach works if the segment boundaries are points on a straight line. In your task, the boundaries of the segment are seconds.
I would add 1 to the ends of the segments and consider the boundaries as points on the number line.
Next, I would separate the code for selecting segments and finding the maximum.
You have a very complex logic and there may be an error. It's hard to keep track of everything.
From memory, you seem to have no problems - well, get another array where you will add {the number of vacancies, the length of the segment}. Put there only segments with a different number of vacancies. Then (or during folding) find the maximum number of vacancies there. And in the last pass, calculate the sum and number of elements in with a given number of vacancies.
Something like this (under-java code, correct yourself):

// class Segment: имеет length и count.
// result - arrayList of Segment
// arrayList содержит MyClass отсортированные по X границы отрезков (Y= +1 для начала и -1 для конца. Концы отрезков имеют сдвинутую на +1 X).

prev_x = arrayList[0].GetX();
cnt = 0;
for (MyClass mc : arrayList)  {
  cur_length = mc.GetX() - prev_x;
  // рассматриваем отрезок (prev_x, mc.GetX()), не включая границы-точки!
  // Поэтому GetY() прибавляем в конце!
  // пропускаем отрезки нулевой длины - они из-за совпадающих точек и смысла не несут
  if (cur_length > 0) {
   //  новый отрезок добавляем, только если разное количество вакансий.
   if (result.size() == 0 || result[result.size() - 1].cnt != cnt) {
    result.add(new Segment(cur_length, cnt);
   } else {
      result[result.size()-1].length += cur_length;
   }
   cnt += mc.GetY();
   prev_x = mc.GetX();
}
max = 0;
for (Segment s : result) {
  if (s.cnt > max) max = s.cnt;
}
length = 0;
total = 0;
for (Segment s : result) {
  if (s.cnt == max) {
    length += s.length;
    total += 1;
  }
}

// print total length.