8
votes
Accepted
How many range are completely inside a given range
I've given an answer to the question with the similar idea here. I'll recall the most important parts of the data structure in this answer. It looks similar to the solution with wavelet trees by Jouni ...
- 887
8
votes
Accepted
Best algorithm to find "deepest" interval
Here's an n log n algorithm:
Convert the intervals into a sorted collection of start and end events. O(n log n)
Initialize a depth value and deepest value to zero, and iterate the collection in ...
- 338
6
votes
Accepted
Returning random integer from interval based on last result and a seed
I suggest you pick a random permutation on the range $[a,b]$, i.e., a bijective function $\pi:[a,b]\to [a,b]$. Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and ...
D.W.♦
- 156k
5
votes
Accepted
Data structure for set of intervals - query for all intervals contains given point
There are many algorithms for this kind of problem. See, e.g., segment trees and interval trees. The kind of query you mention is known as a "stabbing query".
A segment tree takes $O(n \lg n)$ ...
D.W.♦
- 156k
5
votes
Accepted
Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$
(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly ...
- 1,110
4
votes
Accepted
Efficiently locating the maximum value in interval over large amounts of data points
This can be solved with a balanced binary tree. Each such query can be answered in $O(\lg n)$ time.
Build a balanced binary tree, where each leaf holds a point, and the tree is keyed on the $x$-...
D.W.♦
- 156k
4
votes
How many range are completely inside a given range
There are probably existing data structures for this problem, but I am not familiar with them. Instead, I will just create something with the tools I am familiar with.
Assume that the ranges are ...
- 462
4
votes
Accepted
Are IEEE floating point numbers intervals or point values?
That has been long established. Most IEEE 754 floating point numbers represent exactly one real number. The exceptions are +0 and -0, +Inf and -Inf, and NaN with special meanings. (Thanks for one ...
- 28.3k
4
votes
Accepted
Can we find size of total interval in O(N)
There is a simple $O(n\log n)$ algorithm based on sorting all the endpoints of the intervals. I will describe a more sophisticated algorithm, which outputs the union of the input intervals as a union ...
- 275k
4
votes
Computing overlap of intervals in an integer programming framework
By overlap I understand its length (no its coordinates) since you didn't specify how to handle no overlap case.
First you need to know whether $x_1\le y_1$ which is just a comparison.
Next, you ...
- 376
4
votes
Accepted
Finding an interval in a binary search tree that contains a point
You can't find a better algorithm for your problem using comparisons, because a lower bound of $\Omega(\log n)$ can be proven for these setings (proof below).
What you can do is some minor ...
- 1,659
4
votes
Accepted
Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?
Your problem is the same as interval graph coloring.
There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.
- 275k
4
votes
Algorithm To Compute The Gaps Between A Set of Intervals
I'd like to propose a quite simple algorithm as well. The idea is this: we're going to place open and close parentheses on the number line at the boundaries of each interval. For example, for the ...
- 1,258
4
votes
Accepted
Greedy filling unit intervals
The greedy algorithm
Let $result$ be an empty set and let $last\_interval$ be none.
For each $num$ in sorted $X$:
If $num$ is not covered by the last interval:
let $last\_interval$ be the interval ...
- 38.6k
3
votes
Accepted
Compute lebesgue measure of set of intervals
You can solve this in $O(n \log n)$ time. Here is an algorithm. Sort the intervals by their left endpoint ($x$-value), in increasing value. At each stage, if the first interval is disjoint from the ...
D.W.♦
- 156k
3
votes
Accepted
Find longest overlapping interval
You're just a step away from the answer.
Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, ...
- 515
3
votes
Accepted
Algorithm To Compute The Gaps Between A Set of Intervals
The key to prove your algorithm is correct is to find enough invariants of the loop, step 4 so that we apply use mathematical induction.
Let $I_1, I_2, \cdots, I_n$ denote the sorted intervals. When ...
- 38.6k
3
votes
Accepted
Choose non-adjacent numbers from intervals
This problem can be regarded as a scheduling problem.
Each interval corresponds to a job. For each interval $[L_i,R_i]$, Let $r_i = L_i$ be the release time, $d_i = R_i + 2$ be the deadline, and $p_i =...
- 2,205
2
votes
Efficient immutable data structure for small multi-sets of integer ranges?
I would suggest looking at interval trees and segment trees. A natural representation is that the data structure contains a union of non-overlapping ranges $[l,u]$ with a multiplicity $m$; the ...
D.W.♦
- 156k
2
votes
Canonical representation of finite maps on non-overlapping finite rational intervals
Here is another solution. You can use the SeqHash data structure in the following paper:
VerSum: Verifiable Computations Over Large Public Logs. Jelle van den Hooff, M. Frans Kaashoek, and Nickolai ...
D.W.♦
- 156k
2
votes
Canonical representation of finite maps on non-overlapping finite rational intervals
It's possible to build a data structure that in practice has $O(\lg n)$ lookup, $O(\lg n)$ insertion, and $O(1)$ equality-tests. I'll describe how below. (If you care about theoretical worst-case ...
D.W.♦
- 156k
2
votes
Accepted
Find all intervals that are contained in a query interval
You were too quick to reject interval trees and segment trees. You can search an segment tree for all intervals that are contained in a query interval $q=[\ell_q,u_q]$, using a straightforward ...
D.W.♦
- 156k
2
votes
Accepted
Check whether an interval is contained in a union of intervals
The problem requires $\Omega(n)$ time. Consider the interval $[A,B] = [0,N]$ and an algorithm for the problem. Whenever the algorithm queries $[S_{i1},S_{i2}]$, it gets the answer $[i-1,i]$. If the ...
- 275k
2
votes
Array of overlaping ranges
Sort all coordinates of intervals (annotated with their significance), and scan them in order.
As an example, in your case you would get
$$
1^{+red},5^{+yellow},7^{+green},8^{-green},9^{-yellow},11^{-...
- 275k
2
votes
Accepted
Matching schedules between users and providers
I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices.
For instance, considring only ...
- 1,758
2
votes
Accepted
How to find the number of intervals containing a point when given a static set of intervals?
It is a very strong assumption that the time it takes to preprocess is not a concern.
Assume each given interval contains both of its endpoints. Otherwise, the solution below can be adapted easily.
...
- 38.6k
2
votes
Accepted
Algorithm for detecting overlaps
I suppose you want to delete as little EmptyEvents as possible.
In that case, you can achieve what you want in O(nlog(n)) time, where ...
- 2,322
2
votes
Algorithm for detecting overlaps
@Tassle algorithm works great but needs more explaining for vectors ordering.
To do so, put all your starting and ending times in a vector and sort
them in increasing order, breaking ties by ...
- 121
2
votes
Minimum unweighted anticlique (independent set) cover / partition
This is precisely the graph coloring problem. Each subset of $C$ is a color, and we are trying to prevent adjacent vertices from having the same color, while minimizing the number of colors used. ...
- 364
2
votes
Accepted
Max clique in interval graph
Interval graphs are chordal graphs, so you can use a linear time algorithm for finding max clique in a chordal graph. This can be done by first finding a perfect elimination ordering, and then using ...
- 1,339
Only top scored, non community-wiki answers of a minimum length are eligible