blocks|key|1486508|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|entityMap^0^^$0|@$1|2|3|-4|4|5|6|B|7|@]|8|@]|9|$]]]|A|$]]

The Problem

You have a set of ranges, in the fewest number of lines, display each range so that intersecting/adjacent ranges are on different lines.

Natural Buckets

Based on the description ranges fall into natural buckets. That is the only ranges that mater are those that are adjacent to or intersect with itself.

<ol>
<li>Pick a range</li>
<li>If it intersects/adjoins a pre-existing bucket.

<ul>
<li>Add the range to the bucket and extend the left/right edge of the bucket.</li>
<li>Keep the ranges within the bucket sorted by either the left or right edge.</li>
<li>If the left/right edge of the bucket shifts check for and merge with the prior/next bucket if it now adjoins/intersects (merging is a simple concatenation of the sorted contents).</li>
</ul></li>
<li>If it does not intersect/adjoin a pre-existing bucket. 

<ul>
<li>Create a new bucket with the same left/right edge as the range.</li>
<li>Keep these buckets sorted by their left/right edge (which does not mater as they do not overlap/touch).</li>
</ul></li>
</ol>

This makes something similar to an R*-Tree where each leaf node represents a set of intersecting/adjoining ranges, and leaf-sibling represent the buckets. The nodes above are helpers for efficiently sorting new ranges into the structure.

If the ranges were already presorted by the left and/or right edge, the algorithm can be simplified. If ordered by the left edge:

<ol>
<li>Pick the first range, note this range as the start of the partition.</li>
<li>Skip any range whose right edge is less than or equal to the picked range's right edge. </li>
<li>If a range has a right edge greater than the picked range's right edge, and it intersects/adjoin the picked range.

<ul>
<li>pick this new range, but do not set it as the start of the partition</li>
<li>Resume at step 2.</li>
</ul></li>
<li>If a range has a right edge greater than the picked range's right edge, and it does not intersect/adjoin the picked range.

<ul>
<li>all ranges from the partition start to the range prior to this range form a partition.</li>
<li>Pick this range, note this range as the start of the partition.</li>
<li>Resume at step 2.</li>
</ul></li>
<li>If no range is greater

<ul>
<li>all ranges from the partition start to the end form a partition.</li>
</ul></li>
</ol>

If each bucket contains one range, great display a single line with each range.

Back to the original Problem

Except we now know that every range in the bucket intersects or adjoins with another range in the bucket, and there are N buckets which do not intersect/adjoin each other.

The buckets now are for all intents and purposes independent problems. How many lines a given bucket needs in order to layout, or how it is layed out does not rely on any other bucket. Solving how each lays out its ranges can be parallelised. 

Unfortunately each bucket is still a problem, but worse now because each range within is known to have the intersection/adjoinment property (when the bucket holds 2+ ranges). It is not certain that a single range could be removed that would break this property and allow the bucket to be divided up into smaller buckets. Certainly removing some K ranges would allow this to happen, but again there is no guarantee that K is not N the total number of ranges in the bucket. Obviously another solution is needed.

That being said, if a given range consumes most of the space, it might be presumable that removing it would reduce the number of intersections/adjoinments among the remaining ranges. As the problem is also a visualisation issue, this might make sense as you may have a threshold above which such ranges should be displayed in a particular order. I'm not going to travel down this path, but it would not be too hard to extend the line generation algorithm to assimilate these so as to display the least number of lines necessary.

Lines

One way to convert the bucket into lines is to give each range a line. This does not guarantee the least number of lines, but it is certainly the most lines that can be used to display all applicable ranges. You could imagine that two lines would settle/merge when they don't have overlapping/adjoining ranges, and simply repeat until no more lines could settle. This would give fewer lines, but would not guarantee the least. Why? because it might be possible to merge lines in such a way that makes merging further impossible, but had they been merged differently would allow more merges to occur. Consider:

<pre><code>1: ----| |---| |-------
2: -----| |---------| |---
3: |------|
</code></pre>

Had line 1's 2nd range been merged into line 2 instead, line 3 could have been merged into line 1.

<pre><code>1: ----| |------| |-------
2: -----| |---| |---------| |---
</code></pre>

The least number of lines required, would be the same as the point which has the most intersecting/adjoining ranges. That could be established by uniquely listing the points that make up each range, and tallying the number of intersecting/adjoining ranges. The largest Tally is the least number of lines needed. In the above example, you can see that no point intersects/adjoins more than 2 ranges.

In fact this hints at an efficient algorithm.

<ol>
<li>Take the left most range (if there are several, just pick one maybe pick the longest), assign this range to the first line.</li>
<li>Pick the next left-most range, find an existing line whose right is not intersecting/adjoining the left of the range.

<ul>
<li>If found append the range to the line, as the new range does not justify a new line and because it is the next leftmost and was the only candidate that might justify a new line here.

<ul>
<li>For visual pleasantness if several candidate lines exist pick the one with the most ranges/most points encompased/etc... whichever heuristic makes sense.</li>
</ul></li>
<li>If not found then add this range to a new line, as all the current lines have ranges on their right the intersect/adjoin.</li>
</ul></li>
<li>repeat step 2.</li>
</ol>

Algorithm Complexity

This produces a O(KN) algorithm where K is the max number of lines, and N is the number of ranges, presuming already sorted data. You might be able to play that down by sorting the lines by their right edge reducing the K aspect to near constant, but at the cost resorting the updated line, so I am uncertain about the trade-off there.

The natural bucket technique above is a O(NlogN) algorithm when operating on unsorted ranges, but if the ranges where already sorted by left, or by right could be reduced to a linear O(N) algorithm. Whether or not this partitioning would pay off depends on the K (total lines) versus the N (total ranges) versus the sorted state of the ranges. If the ranges are already sorted (by left or right edge) then its a K vs logN question, if K is expected to be less than LogN go with a straight line construction, otherwise partition first, and assemble the lines per bucket (line merging is trivial O(N)). If the data is not sorted, the cost is O(NlogN) either way, might as well sort into sorted buckets as at least then you'll be reducing K to its absolute minimum per bucket.

I have an array of ranges with start and end timestamps. I want to display those ranges on a graph.

Right now, my naive algorithm gets an array of ranges sorted by their start timestamp and

<ul>
<li>iterate over each range in the sorted array

<ul>
<li>find the first bucket where the last range of the bucket has an end timestamp lower than the start timestamp of the current sample

<ul>
<li>If no such bucket exists, add a new bucket</li>
</ul></li>
<li>add current sample to found bucket</li>
</ul></li>
</ul>

I then use these buckets to fill my graph. Each bucket represents a line on the graph.

<a href="https://i.stack.imgur.com/oGYQp.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/oGYQp.png" alt="enter image description here"></a>

It's a O(n²) algorithm. This works fine for my needs, if not a bit slow when having 50,000+ ranges.

One issue with this algorithm is when a range's end timestamp changes, the algorithm needs to be run for all samples.

For whatever reason, I now want to make a change to how the data is fetched from the database, and due to technical constraints, the data cannot be sorted efficiently.

Please help me think of an efficient algorithm where data does not have to be sorted.

Sorting an array of ranges for display

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我有一系列带有开始和结束时间戳的范围。我想在图表上显示那些范围。现在，我的朴素算法得到了一个范围数组，按照它们的开始时间戳和遍历排序数组中的每个范围查找第一个桶，其中存储桶的最后一个范围的结束时间戳低于当前示例的开始时间戳如果不存在这样的桶，则添加一个新桶。- add current sample to found bucket然后我使用这些桶来填充我的图表。每个桶表示图表上的一条线。📷这是一个

问对范围数组进行排序以供显示
EN

回答 1

Software Engineering用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问对范围数组进行排序以供显示EN