Ускорение кода Python

Question

Имеется задача. В наличии n разных поддонов. У каждого поддона есть ширина и длинна. Поддон p можно поставить на поддон q, только если p целиком помещается на q. Это означает что длина и ширина первого поддона строго меньше длины и ширины второго поддона. Найдите количество поддонов, которые нельзя поставить ни на один другой поддон. Ввод данных осуществляется следующим образом: первой строкой идет n - число поддонов, а потом на каждой строке отдельно параметры для каждого поддона. Пример ввода:

5

1 1

2 10

2 2

3 6

5 4

Суть вопроса: я написал код, он правильно работает, но не проходит по скорости. Как его можно ускорить?

def compare(lhs, rhs):
    return (lhs[0] < rhs[0] and lhs[1] < rhs[1]) or (lhs[0] < rhs[1] and lhs[1] < rhs[0])


def solve():
    from sys import stdout, stdin
    text = stdin.readlines()
    n = int(text[0])
    boxes, counter, st = tuple(tuple(int(item) for item in text[i].split()) for i in range(1, n + 1)), 0, set()
    for box in boxes:
        if box in st:
            counter += 1
        else:
            for comp in boxes:
                if comp not in st and compare(box, comp):
                    st.add(box)
                    counter += 1
                    break
    stdout.write(str(len(boxes) - counter))


solve()

Answer 1

Отсортировать поддоны по длине по убыванию. Если длина одинаковая, то первым идёт поддон с большей шириной (т.е. ширина - вторичный ключ сортировки).

Первый поддон не ставится на другие. Запомним его как Big, счётчик единица. Пройдём по списку по порядку. Если текущий поддон не ставится на Big, то увеличим счётчик, и текущий становится Big.

Сложность O(nlogn)+O(n)=O(nlogn)

Задача эквивалентна задаче о доминирующем наборе точек (математически - эффективность по Парето)

Answer 2

Мое решение работает за O(nlogn), но все равно не проходит Time Limit. Скорее всего это лучшая сложность и тесты придумали идиоты, но доказать Lower Bound я не в силах

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//test it out. Think up different edge cases
public class PalletPlacement {

    static int calculate(List<int[]> pallets) {
        int temp;
        int i;
        for(i = 0; i < pallets.size(); i++) {
            if(pallets.get(i)[0] < pallets.get(i)[1]) {
                temp = pallets.get(i)[0];
                pallets.get(i)[0] = pallets.get(i)[1];
                pallets.get(i)[1] = temp;
            }
        }
        int res = 0;
        Collections.sort(pallets, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o2[1] - o1[1];
            }
        });
        int[] dp = new int[pallets.size()];
        int max = Integer.MIN_VALUE;
        for(int j = pallets.size() - 1; j >= 0; j--) {
            max = Math.max(max, pallets.get(j)[1]);
            dp[j] = max;
        }
        for(i = 0; i < pallets.size(); i++) {
            int start = i + 1;
            int end = pallets.size() - 1;

            while(start <= end) {
                int middle = start + (end - start) / 2;

                if (pallets.get(middle)[0] > pallets.get(i)[0]) {
                    end = middle - 1;
                } else {
                    start = middle + 1;
                }
            }
            if(start >= dp.length || dp[start] <= pallets.get(i)[1]) {
                res++;
            }

        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(reader);
        int n = Integer.parseInt(in.readLine());
        List<int[]> pallets = new ArrayList<>(n);
        for(int i = 0; i < n; i++) {
            String[] split = in.readLine().split(" ");
            int[] temp = new int[2];
            temp[0] = Integer.parseInt(split[0]);
            temp[1] = Integer.parseInt(split[1]);
            pallets.add(temp);
        }
        int res = calculate(pallets);
        System.out.println(res);
    }
}

БЛОГ НА HUSL

Ускорение кода Python

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