Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #11 (permalink)  
Старый 15.10.2021, 17:05
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,004

если прям нужно получить максимум отрезков не одной из ордеров, то можно так:

<pre>
<script>

const data = [
    {
        x1: 1,
        x2: 4,
        order: 0
    },
    {         // Добавил этот
        x1: 5,
        x2: 11,
        order: 0
    },
    {
        x1: 7,
        x2: 10,
        order: 0
    },
    {
        x1: 5,
        x2: 8,
        order: 0
    },
    {
        x1: 10,
        x2: 13,
        order: 0
    },
    {
        x1: 8,
        x2: 11,
        order: 0
    },
    {
        x1: 8,
        x2: 11,
        order: 0
    }
];

function updateOrders(data) {
    if (!data || !data.length) {
        return;
    }
    const arr = data.slice().sort((a, b) => a.x2 - b.x2);

    let order = 1;
    while (arr.length) {
        let lastX2 = -Infinity;
        let p = 0;
        for (let i = 0; i < arr.length; ++i) {
            const item = arr[p] = arr[i];
            if (item.x1 >= lastX2) {
                lastX2 = item.x2;
                item.order = order;
            } else {
                p++;
            }
        }
        arr.length = p;
        order++;
    }
}
updateOrders(data);

document.write(JSON.stringify(data, "", 2))
</script>
</pre>


но тут уже асимптотика в худшем случае будет O(N^2).

сортируем по х2, далее обходим массив и заполняем первый ордер (заполненные выкидываются из отсортированного массива). Если массив не опустел, повторяем. Худший случай - когда будет N ордеров, по одному в каждом: каждый раз, добавив первый поинт в ордер, придется бесполезно обойти все другие оставшиеся поинты.

Последний раз редактировалось Alexandroppolus, 15.10.2021 в 17:07.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Error: ER_BAD_FIELD_ERROR: Unknown column 'priсe' in 'order clause' riaron Node.JS 1 16.09.2020 23:27
Как правильно прочитать запрос? gsdev99 Node.JS 3 30.06.2019 04:15
Сортировка массива с объектами на javascript sergiu920 Элементы интерфейса 2 07.12.2018 09:47
как правильно обращаться к свойствам объект внутри самого объекта ? mitiya Общие вопросы Javascript 12 25.04.2015 21:18
Adobe Acrobat Reader 9 Pro cheap order online Rodivazzio Элементы интерфейса 0 04.07.2009 02:55