Questions tagged [intervals]
The intervals tag has no usage guidance.
98
questions
0
votes
1answer
249 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 ...
3
votes
1answer
44 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$ ...
1
vote
0answers
28 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 ...
3
votes
1answer
102 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 ...
4
votes
0answers
58 views
Efficient 2d interval merging product
Suppose I have two tables of 2d intervals (axis-aligned rectangles) with values attributed to each interval.
...
7
votes
0answers
147 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$...
1
vote
0answers
22 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
...
3
votes
1answer
97 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 ...
5
votes
0answers
55 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 ...
1
vote
1answer
33 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 ...
0
votes
1answer
34 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:
...
1
vote
1answer
36 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 ...
2
votes
2answers
84 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$ ...
1
vote
1answer
93 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
1answer
80 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?
...
1
vote
1answer
34 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
2answers
344 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 ...
0
votes
1answer
99 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 ...
4
votes
1answer
202 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 ...
1
vote
0answers
108 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 ...
2
votes
1answer
89 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 ...
1
vote
1answer
46 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 ...
2
votes
1answer
48 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)...
2
votes
1answer
47 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 ...
2
votes
1answer
93 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 ...
1
vote
2answers
405 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. ...
9
votes
1answer
313 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{...
2
votes
1answer
68 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 ...
3
votes
1answer
45 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 ...
2
votes
1answer
59 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 ...
3
votes
1answer
48 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]]...
0
votes
0answers
237 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
2answers
192 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 ...
3
votes
2answers
321 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 ...
3
votes
0answers
189 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, ...
1
vote
1answer
407 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 ...
1
vote
1answer
451 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 ...
0
votes
1answer
241 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
2answers
184 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 ...
1
vote
1answer
103 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 ...
2
votes
1answer
126 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 ...
1
vote
0answers
48 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 (...
0
votes
2answers
50 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 ...
1
vote
0answers
41 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 ...
2
votes
1answer
68 views
Data Structures - Segment Trees
I was learning about segment trees and came across this:
We have an array arr[0 . . . n-1]. We should be able to
1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1
...
1
vote
1answer
101 views
(M)ILP overlap of two intervals
I got an ILP Model where $c_i$ represents the starting time for a visit$_i$.
$c_i$ is already constraint by a number of constraints, one is $c_i > 0$.
I have now outside of my model 0 or multiple ...
0
votes
1answer
356 views
interval scheduling algorithm
can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this ...
1
vote
1answer
101 views
Variant of interval scheduling with varying task durations
I am probably just missing the correct term for my problem to find the solution but here it goes:
I have a set of tasks with a given duration and an interval for each task in which it has to be ...
2
votes
1answer
20 views
Array of overlaping ranges
Consider that I have an array of ranges and I want to transform it to the new array that represents the ranges that any range is in.
Example:
Ranges:
[red: [1,11], black: [15,16],yellow: [5,9], ...
4
votes
0answers
51 views
Compile-time error control vs. interval arithmetic?
I use interval arithmetic for reliable computing. Now, a procedure coded in a good implementation of interval arithmetic takes perhaps about eight times as much as the same procedure carried out ...
