Проставить правильно order
У меня есть массив объектов https://codesandbox.io/s/js-playgrou...=/src/index.js
нужно проставить каждому order так, чтобы отрезки не пересекались пример на картинке https://prnt.sc/1w8175p |
valya2021,
каковы приоритеты? первым шагом напрашивается сортировка по нижней границе, но тогда в самый верхний ордер попадут отрезки 2 и 4. Это допустимо? правильно я понимаю, что надо как можно меньше ордеров? |
нужно разместить как можно больше отрезков на одной прямой (Y)
если отрезки пересекаться нужно следующий переместить на низ (Y+1) |
вот код. Но не все кейсы покрывает(
let order = 0
data.map((item, index) => {
if (index > 0 && data[index - 1].x2 >= item.x1) {
order += 1
} else {
order = 0
}
}
|
навскидку тут всё просто: сортируем отрезки по левому краю. Далее держим приоритетную очередь ордеров (на вершине - тот ордер, у которого левее других правый край последнего отрезка). Обходим отсортированный массив, берем из него очередной отрезок. Если у этого отрезка левый край вписывается в ордер из вершины очереди, то добавляем в этот ордер, просеиваем ордер вниз. Если не вписывается, создаем новый ордер, добавляем в него отрезок, ордер добавляем в очередь. Время работы O(N ln(N)).
Осталось закодить) |
вот у мене и проблема это все закодить(
забыл сказать, сортировка возможна только по 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>
|
<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>
|
всем спасибо!!!
Все работает |
Не....
Ни фига не работает.
<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>
Есть условие Цитата:
А отрезку 1 - order = 1. А наши алгоритмы размещают максимум 2 отрезка на прямой. |
если прям нужно получить максимум отрезков не одной из ордеров, то можно так:
<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 ордеров, по одному в каждом: каждый раз, добавив первый поинт в ордер, придется бесполезно обойти все другие оставшиеся поинты. |
| Часовой пояс GMT +3, время: 08:18. |