Проставить правильно order

[valya2021]

У меня есть массив объектов https://codesandbox.io/s/js-playgrou...=/src/index.js

нужно проставить каждому order так, чтобы отрезки не пересекались
пример на картинке


https://prnt.sc/1w8175p

[Alexandroppolus]

valya2021,
каковы приоритеты? первым шагом напрашивается сортировка по нижней границе, но тогда в самый верхний ордер попадут отрезки 2 и 4. Это допустимо?
правильно я понимаю, что надо как можно меньше ордеров?

[valya2021]

нужно разместить как можно больше отрезков на одной прямой (Y)
если отрезки пересекаться нужно следующий переместить на низ (Y+1)

[valya2021]

вот код. Но не все кейсы покрывает(

let order = 0
data.map((item, index) => {
    if (index > 0 && data[index - 1].x2 >= item.x1) {
        order += 1
    } else {
        order = 0
    }
}

[Alexandroppolus]

навскидку тут всё просто: сортируем отрезки по левому краю. Далее держим приоритетную очередь ордеров (на вершине - тот ордер, у которого левее других правый край последнего отрезка). Обходим отсортированный массив, берем из него очередной отрезок. Если у этого отрезка левый край вписывается в ордер из вершины очереди, то добавляем в этот ордер, просеиваем ордер вниз. Если не вписывается, создаем новый ордер, добавляем в него отрезок, ордер добавляем в очередь. Время работы O(N ln(N)).
Осталось закодить)

[valya2021]

вот у мене и проблема это все закодить(
забыл сказать, сортировка возможна только по x1

[рони]

valya2021,

<pre>
    <script>
        const data = [{
                x1: 1,
                x2: 4,
                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
            }
        ];


        let arr = Object.keys(data);
        let order = 1;
        while (arr.length) {
            let min = data[arr[0]].x1;
            for (let i = 0; i < arr.length;) {
                let k = arr[i];
                let {
                    x1,
                    x2
                } = data[k];
                if (x1 >= min) {
                    data[k].order = order;
                    min = x2;
                    arr.splice(i, 1);
                } else i++
            }
            order++;
        }

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

[voraa]

<pre>
<script>
    const data = [{
                x1: 1,
                x2: 4,
                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
            }
        ];
            
let orders = [];

data.forEach ( (x, i) => {
    let no = orders.findIndex (o => o.every (ot => data[ot].x1>=x.x2 || data[ot].x2 <= x.x1) );
   if (no>=0) 
      orders[no].push(i);
   else 
     no = orders.push([i]) - 1;
  x.order = no;
} )

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

[valya2021]

всем спасибо!!!
Все работает

[voraa]

Не....
Ни фига не работает.

<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
            }
        ];
        
        
let orders = []
data.forEach ((x, i) => {
 let no = orders.findIndex (o => o.every (ot => data[ot].x1>=x.x2 || data[ot].x2 <= x.x1) );
 if (no>=0) 
    orders[no].push(i);
  else 
    no = orders.push([i]) - 1;
  x.order = no;

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

Есть условие

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

Можно назначить order = 0 (у Рони 1) трем отрезкам 0, 2 и 5
А отрезку 1 - order = 1.

А наши алгоритмы размещают максимум 2 отрезка на прямой.