Ускорение Алгоритма, чтобы выйти из 1 секунды

Question

Я решаю задачу, у меня проблема в том, что на определенном тесте выходит ошибка TL(time limit),(код представлен после условия), я не знаю как можно было бы ускорить алгоритм чтобы проходили тесты, может быть есть ошибка в логике моей - этого отрицать не могу.

Условие задачи: Даны два массива a и b, длины N, состоящие из целых чисел. Рассмотрим множество, состоящие из отрезков, соединяющие точки (0, ai) и (1, bi) для 1 <= i <= N. Найдите количество отрезков множества, которые не пересекаются с другими отрезками.

Пересекающимися являются отрезки у которых есть хотя бы одна общая точка, то есть отрезки имеющие одинаковый конец пересекаются.

формат ВВОДА

в первой строке вводится N (1 <= N <= 3 * 10^5) - количество отрезков. Далее в N строках по 2 целых числа разделенных пробелом ai и bi (1 <= ai, bi <= 2 * N), задающие координаты i отрезка. Гарантируются что все отрезки заданные в вводе различны, то есть при i != j выполнено не менее одного из условий ai != aj и bi != bj

КОД:

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Map<Integer, ArrayList<Integer>> nums = new HashMap<>();
        int amount = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < amount; i++) {
            String[] point = sc.nextLine().split(" ");
            int x = Integer.parseInt(point[0]);
            int y = Integer.parseInt(point[1]);
            if (!nums.containsKey(x)) {
                nums.put(x, new ArrayList<>());
            }
            nums.get(x).add(y);
        }

        int count = 0;
        for (int key1 : nums.keySet()) {
            boolean intersects = false;
            ArrayList<Integer> values1 = nums.get(key1);
            for (int key2 : nums.keySet()) {
                if (key1 != key2) {
                    ArrayList<Integer> values2 = nums.get(key2);
                    for (int value1 : values1) {
                        for (int value2 : values2) {
                            if ((key1 < key2 && value1 >= value2) || (key1 > key2 && value2 >= value1)) {
                                intersects = true;
                                break;
                            }
                        }
                        if (intersects) {
                            break;
                        }
                    }
                    if (intersects) {
                        break;
                    }
                }
            }
            if (!intersects) {
                count++;
            }
        }

        System.out.println(count);
    }
}

Answer 1

Вам не надо сравнивать всё со всем.

Поглядите на вашу картинку

Допустим, вы идете слева направо по координате (0,ai), вы видите, что если a0=1 и b0=4, то любой другой отрезок где ai >= a0 и bi<=b0 будет пересекаться с первым отрезком.

Поскольку мы идем слева направо, значит обрабатывая очредную пару ai, bi, чтобы понять, пересекается эта пара с другой парой, нам надо только знать среди всех предыдущих значений максимальный aMax и bMax. Если ai == aMax - то отрезки пересекаются с предудщими в точке ai. Если bi <= bmax - то отрезок bi пересекается с каким то отрезком который уже обработан.

Таким образом получаем линейный алгоритм (если не считать сортировку за NlogN). Пример на C#, где я прохожу сначала слева направо, потом справа налево.

public int[][] NotIntersects(int[][] data)
{
    Array.Sort(data, Comparer<int[]>.Create( (a,b) => a[0].CompareTo(b[0]) ));
    
    var edge = data[0][1];  
    var idexes = new HashSet<int>();
    
    for(int i=1; i<data.Length; i++)
    {
        if (data[i][1] <= edge || data[i][0] == data[i-1][0]) idexes.Add(i);
        edge = Math.Max(edge, data[i][1]);
    }
    
    edge = data[data.Length-1][1];

    for (int i = data.Length - 2; i >=0; i--)
    {
        if (data[i][1] >= edge || data[i][0] == data[i+1][0]) idexes.Add(i);
        edge = Math.Min(edge, data[i][1]);
    }
    
    return data.Where((x, i) => !idexes.Contains(i)).ToArray();
}

Проверка

NotIntersects(new[] { 
    new[] { 1, 4 }, 
    new[] { 2, 5 }, 
    new[] { 3, 1 }, 
    new[] { 4, 5 }, 
    new[] { 5, 6 } })
    .Dump();

Вывод

Answer 2

Пусть a_i - нижние концы отрезков, построим индекс i_k такой что последовательность a_{i_k} не убывает.

Аналогично, индекс j_k делает неубывающей последовательность b_{j_k}.

Чтобы отрезок (a_m, b_m) был одиноким, надо чтобы все остальные отрезки были целиком слева или справа от него. Пусть слева от него k отрезков, а все остальные справа. Тогда i_k = m - слева от нижнего конца одинокого отрезка k нижних концов отрезков. Аналогично, j_k = m - слева от верхнего конца одинокого отрезка k верхних концов отрезков. Конкретное значение m не важно. Важно что у всех одиноких отрезков i_k = j_k.

У одинокого отрезка нижние концы его соседей с ним не совпадают: a_{i_k-1} < a_{i_k} < a_{i_k+1}. Аналогично верхние концы не совпадают: b_{j_k-1} < b_{j_k} < b_{j_k+1}.

Итерируемся по k. Все отрезки, которые начались перед одиноким отрезком, должны перед ним и закончится. Для этого заведём массив флагов по числу отрезков. Когда отрезок начинается или заканчивается, соответствующий флаг инвертируется. Перед одиноким отрезком все флаги должны быть сброшены.

Программа ниже воплощает эти три идеи. Время работы O(nlogn).

import java.util.*;

public class Temp {
    private static class Index {
        private final boolean[] flags;
        private final int n;
        private final int[] a;
        private final int[] i; // a[i[k]] перечислены по возрастанию

        public Index(boolean[] flags, int[] a) {
            this.flags = flags;
            this.n = a.length;
            this.a = a;
            Integer[] index = new Integer[this.n];
            for (int i = 0; i < this.n; ++i) {
                index[i] = i;
            }
            Arrays.sort(index, Comparator.comparingInt(i -> a[i]));
            this.i = new int[this.n];
            for (int k = 0; k < this.n; ++k) {
                this.i[k] = index[k];
            }
        }

        // инвертирует флаг для отрезка на позиции k
        // возвращает один, если флаг установлен
        // возвращает минус один, если флаг снят
        public int flip(int k) {
            flags[i[k]] = !flags[i[k]];
            return (flags[i[k]]) ? 1 : -1;
        }

        // индекс отрезка на позиции k
        public int i(int k) {
            return i[k];
        }

        // конец отрезка на позиции k не пересекается с другими отрезками 
        public boolean distinct(int k) {
            return 
                (k == 0     || a[i[k - 1]] < a[i[k]]              ) &&
                (k == n - 1 ||               a[i[k]] < a[i[k + 1]])
            ;
        }
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = s.nextInt();
            b[i] = s.nextInt();
        }
        boolean[] flags = new boolean[n];
        Index ia = new Index(flags, a);
        Index ib = new Index(flags, b);

        int answer = 0; // число одиноких отрезков
        int nFlags = 0; // число отрезков, которые начались и не закончились
        for (int k = 0; k < n; ++k) {
            if (
                nFlags == 0        && // все отрезки завершились
                ia.i(k) == ib.i(k) && // это концы одного отрезка
                ia.distinct(k)     && // конец a не пересекается с другими
                ib.distinct(k)        // конец b не пересекается с другими
            ) {
                ++answer;
            }
            // перевернуть флаги и поправить счётчик установленных флагов
            nFlags += ia.flip(k) + ib.flip(k);
        }
        System.out.println(answer);
    }
}

БЛОГ НА HUSL

Ускорение Алгоритма, чтобы выйти из 1 секунды

Ответы (2 шт):