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 ...
Ivan Smirnov's user avatar
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 ...
DMGregory's user avatar
  • 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.'s user avatar
  • 159k
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 ...
integrator's user avatar
  • 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.'s user avatar
  • 159k
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 ...
gnasher729's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
user1543037's user avatar
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 ...
Jouni Sirén's user avatar
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 ...
lox's user avatar
  • 1,669
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.
Yuval Filmus's user avatar
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 ...
Daniel Wagner's user avatar
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 ...
John L.'s user avatar
  • 39k
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']$, ...
aaaaajack's user avatar
  • 515
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.'s user avatar
  • 159k
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 ...
John L.'s user avatar
  • 39k
3 votes

Maximum interval scheduling - Circular Variation

Yes. What we need to do is, basically, running the $O(n^2)$ algorithm provided in the question, but without unnecessary intervals and redundant steps. Here is the gist of an $O(n\log n)$ algorithm. ...
John L.'s user avatar
  • 39k
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 =...
pcpthm's user avatar
  • 2,348
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.'s user avatar
  • 159k
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.'s user avatar
  • 159k
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.'s user avatar
  • 159k
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 ...
Yuval Filmus's user avatar
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.'s user avatar
  • 159k
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^{-...
Yuval Filmus's user avatar
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 ...
Optidad's user avatar
  • 1,788
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. ...
John L.'s user avatar
  • 39k
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 ...
Tassle's user avatar
  • 2,522
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 ...
Eduardo Yamauchi's user avatar
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. ...
taktoa's user avatar
  • 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 ...
Laakeri's user avatar
  • 1,339

Only top scored, non community-wiki answers of a minimum length are eligible