Questions tagged [intervals]
The intervals tag has no usage guidance.
104
questions
1
vote
0
answers
22
views
Find if union of discrete intervals with holes covers the whole interval space
There is a whole space interval [0,128]
And several discrete sequences like:
...
- 199
3
votes
1
answer
148
views
Greedy filling unit intervals
I have unit intervals given such as $I = \{\{s_1, s_1 + 1\}, ..., \{s_k, s_k+1\}\}$ ($\forall s_i \in \mathbb{R}$). I am given a list of $X$ reals, such that each of the reals belongs to at least one ...
- 149
1
vote
1
answer
33
views
Is there a data structure for lazy-loading time-series data?
I am writing a UI that needs to display a chat log, similar to Slack and Discord. In addition to being able to scroll and lazy-fetch additional pages in either direction, I need to be able to jump to ...
3
votes
1
answer
56
views
Bisecting Intervals of floating point numbers containing 0 and infinity fairly
It is seldom considered that floating points are not evenly distributed in the real number line. I've been working with interval arithmetic and noticed when bisecting $[a,b]$ on the real number line ...
- 133
0
votes
1
answer
46
views
Interval Tree by Augmenting an AVL Tree
According to Wikipedia: An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. ...
- 125
1
vote
0
answers
31
views
Data structure for quickly obtaining all axis-aligned rectangles completely within rectangular region
I'm stuck on a homework assignment. There are $n$ axis aligned rectangles and we need to find a data structure of size $O(n \log^2 n)$ and query time $O(\log^3 n + k)$ that can give all rectangles ...
- 11
0
votes
1
answer
318
views
Best algorithm to find "deepest" interval
Let's say I have a list of intervals on a number line. The "depth" of a point on this number line corresponds to the number of intervals in the list that contain it [the point].
So for ...
- 111
3
votes
1
answer
62
views
Weighted maximum match for intervals
Say I have two sets of intervals sorted by time $I_1=[(x_1, y_1),... (x_n, y_n)]$ and $I_2 = [(a_1, b_1)... (a_m, b_m)]$. where $x, y, a, b$ are times in seconds. None of the intervals within $I_1$ ...
- 155
1
vote
0
answers
29
views
Social Networking Disease Transmission
You are given an undirected graph (social network) in which each edge $e = (v, v')$ has an interval $I_e = [l_e, u_e]$ on it. The meaning is that you know that $v$ and $v'$
met at some point during ...
- 23
3
votes
1
answer
385
views
Maximum interval scheduling - Circular Variation
Consider a variant of interval scheduling except now the intervals are arcs on a circle. The goal is to find the maximum number of arcs that do not overlap. Let $C$ be the circle
on the plane centered ...
- 503
4
votes
0
answers
70
views
Efficient 2d interval merging product
Suppose I have two tables of 2d intervals (axis-aligned rectangles) with values attributed to each interval.
...
- 215
7
votes
0
answers
160
views
Finding a rainbow independent set in a circle
Inside the interval $[0,1]$, there are $n^2$ intervals of $n$ different colors: $n$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $n$...
- 5,664
1
vote
0
answers
24
views
Finding max values at a point given a list of ranges
In coding competitions I usually see problems that involve dealing with values in given ranges. A typical example is, given a list of 3-tuples defined as so
...
- 111
3
votes
1
answer
133
views
Merging Tuples of Intervals
Suppose I have a list of tuples. Each tuple contains 2 intervals. The intervals in each tuple have nothing to do with each other. I would like to find a smaller list of tupels that covers all elements ...
- 53
7
votes
0
answers
91
views
Optimality of DSATUR on interval graphs
The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of different ...
- 6,942
1
vote
1
answer
249
views
Minimal number of intervals that covers $\{1,...,k\}$
Let $F$ be a family of sets of consecutive integers in $\{1,…,k\}$ that is closed under taking subintervals, i.e. for any $a≤b≤c≤d$, if $\{a,…,d\} \in F$, then $\{b,…,c\} \in F$ also. Find a minimum ...
- 13
0
votes
1
answer
37
views
What's the name of this packing problem?
I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping.
For example if I have these intervals:
...
- 101
1
vote
1
answer
57
views
Intersection of Decision Tree Boundaries in Higher Dimensions
I have trained two binary decision tree classifiers with splits in $\mathbb{R}^4$. Same data, but from two different patches. Now, I want to find the exact intervals where the two trees disagree.
The ...
- 11
2
votes
2
answers
122
views
Data structure for interval subset queries
I have a set $S$ of intervals. I'd like to store them in a data structure, so that I can handle the following query efficiently: given a query interval $q$, count the number of intervals $s \in S$ ...
D.W.♦
- 140k
1
vote
1
answer
128
views
Find minimum number of points which intersect overlapping arcs
Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time.
I'm having some trouble proving ...
2
votes
1
answer
129
views
How can I implement a data structure which calculates the number of nested intervals in sub-linear time?
Is there a data structure which can maintain a list of intervals and the following operations?
...
- 43
1
vote
1
answer
75
views
What does it mean that a set of intervals is sorted by the right and left endpoints?
While reading a paper (On the k-coloring of intervals), I came upon the following description:
"Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are ...
2
votes
2
answers
529
views
Algorithm To Compute The Gaps Between A Set of Intervals
Problem
Given a set of intervals with possibly non-distinct start and end points, find all maximal gaps. A gap is defined as an interval that does not overlap with any given interval. All endpoints ...
- 123
0
votes
1
answer
142
views
Intervals Collision Detection Algorithm
Given a collection of non-empty intervals [a,b), where a/b are integers in some finite range (ex. 0...100) and a is less than b, can you find an algorithm that will detect all intervals that exhibit ...
- 103
4
votes
1
answer
242
views
How to group intervals which overlap by some amount?
I have an algorithm that generates a list of intervals. The algorithm is run m times. Lets mark the intervals as tuples (s1, e1), (s2, e2), .., (sn, en). It is ...
- 151
1
vote
0
answers
134
views
Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree
I am curently working on automatic label placement, so for evaluating a model, one metric is to calculate the Area A:
A is the sum of every part of a rectangle covered by another. So if two rectangle ...
- 11
2
votes
1
answer
97
views
Returning random integer from interval based on last result and a seed
Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are ...
- 31
1
vote
1
answer
60
views
Is there an Interval Tree which supports O(1) dynamic space requirements for queries?
I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key).
In general ...
- 121
2
votes
1
answer
59
views
Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?
If an array $A[1 \ldots N]$ is represented using a segment tree having sets in each interval, why does a range query $[L\ldots R]$ returns at most $\lceil \log_2{N} \rceil$ sets (or disjoint intervals)...
- 23
3
votes
1
answer
58
views
Interval sorting that avoids covering
I have a collection of intervals and I want to sort them so that the order is interpreted as a sort of "z-index". That is, a given interval may or may not be "visible" depending on whether the merge ...
- 33
2
votes
1
answer
106
views
Schedule X Classes In N Classrooms
I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...)
I am really out of thoughts
I have X number of classes ...
- 21
2
votes
2
answers
534
views
Max clique in interval graph
According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. ...
- 364
9
votes
1
answer
342
views
2D interval scheduling problem
Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
- 364
2
votes
1
answer
77
views
Minimum unweighted anticlique (independent set) cover / partition
Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously ...
- 364
3
votes
1
answer
54
views
Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?
Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$.
I want to find a minimum cardinality partition of ...
- 227
2
votes
1
answer
60
views
Queries on knapsack
Given items with weights $w_{1}, w_{2}, \dots, w_{n}$ and queries of form $(l, r, w)$ asking for possibility to find a subset of items $w_{l}, w_{l + 1}, \dots, w_{r}$ with total weight $w$, how to ...
- 21
3
votes
1
answer
108
views
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$
Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$.
I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]...
- 177
0
votes
0
answers
261
views
How Segment trees are used to answer interval stabbing query?
Can anybody explain to me how segment trees are used to answer interval stabbing queries? I have searched and searched and only come with the beginning of the line.
From my understanding I need to ...
0
votes
2
answers
275
views
largest subset of pairwise intersecting intervals [closed]
Given a set of intervals on the real line, compute the largest subset of pairwise
intersecting intervals (an interval in the subset must intersect with every other interval
in the subset). Design a ...
- 11
3
votes
2
answers
375
views
Algorithm for detecting overlaps
This is a real-world application, not a student assignment.
Suppose a list of events of that have startTime and endTime, and ...
- 85
3
votes
0
answers
204
views
Algorithm for answering queries of the type "largest interval contained in the given interval"
I have been wondering over the following problem:
Given a set $S$ of intervals on the number line. We can do two operations on them:
Add a new interval $[l_i,r_i]$ to $S$
Given an interval $[l_j, ...
- 131
1
vote
1
answer
533
views
How to find the number of intervals containing a point when given a static set of intervals?
I've seen similar questions around here but I'm trying to address this problem with a slight change and maybe it makes it easier to solve.
I'm given a set of intervals $\{s_1,s_2,...,s_n\}$ where ...
- 317
2
votes
1
answer
555
views
Finding an interval in a binary search tree that contains a point
I have a binary search tree where nodes are non-overlapping intervals. I'm given a point, and I need to determine which interval the point belongs to (if any). This is easy to do because I can compare ...
- 203
0
votes
1
answer
379
views
Proof for optimal interval scheduling using a Greedy Approach
You are given a set of n jobs, where each job j is associated with a size
s(how much time it takes to process the job) and a weight w(how important the
job is). Suppose you have only one machine ...
1
vote
2
answers
260
views
Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval
Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair?
The naive approach is ...
- 163
1
vote
1
answer
124
views
Matching schedules between users and providers
I have a problem I've been dealing for the past few days, and I'm pretty stuck.
Each user has a schedule for a given week, such as ...
- 48
2
votes
1
answer
139
views
Minimal set of subintervals that 'covers' any subinterval in K subintervals
I have a big interval $I = [a, b]$ of size n.
I want an asymptotically minimal set of subintervals of $I$ (let's call it $S$) one can use to construct any subinterval of $I$, by concatenating at most ...
- 21
1
vote
0
answers
49
views
Efficient data structure for multidimensional searching on intervals and keys
I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (...
- 11
0
votes
2
answers
53
views
Sorted unsigned integer intervals tree structure
The goal is to store sorted unsigned integer intervals that can overlap only in the boundaries, e.g., |0–10|10–50|100–110|110–200|. This structure will be created ...
- 103
1
vote
0
answers
47
views
Sort-of interval scheduling
The Problem
I have a set of sets of time intervals (hour, minute, day of the week). I want to select exactly one interval from each of set, and I want to minimize...
the number of pairwise ...
- 121