Questions tagged [intervals]
The intervals tag has no usage guidance.
116
questions
1
vote
1
answer
37
views
Dynamic Programming problem about intervals
This is algorithms and data structures assignment and I have been thinking 3 days about it.
You are given N sections, placed on numeric axis. Numeric axis is divided by unit intervals. Each section in ...
- 11
0
votes
0
answers
19
views
Intervals with costs and limited resources, dynamic programming
I have been trying to solve the following problem. I have n intervals each with a cost.I want to choose a subset of the intervals that maximizes the cost but with the following constraint. Each ...
- 3
1
vote
0
answers
93
views
complexity of graph matching with order constraint
Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$.
Find the maximum $k$ such that ...
- 11
-1
votes
2
answers
64
views
Given m intervals and an array of integers, your task is to minimize the number of operations in which you can make the elements of the array nonposit
You are given the number $m$ and $m$ intervals of the form $a_i, b_i, v_i$, where $a_i<=b_i$ and $v_i>0$ and also a number $n$ and an array $s$ of length $n$, where $s_i>0$. In one operation ...
- 1
0
votes
1
answer
27
views
Is minimum interval hitting problem NP-HARD?
Consider this problem:
We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in ...
0
votes
1
answer
203
views
Proving the correctness of a greedy algorithm for the Circular Scheduling Problem
Consider the following variation on the Interval Scheduling Problem
You have a processor that can operate 24 hours a day, every day. People
submit requests to run daily jobs on the processor. Each ...
2
votes
2
answers
610
views
Select a subset of k intervals which form maximum length if we take union of these k intervals
Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals.
Note that there are 2 cases ...
- 123
1
vote
1
answer
99
views
pairing numbers and intervals
subject: pairing numbers and intervals
Let NUMBERS be a list of n integer numbers. The numbers are listed in no specific order. ...
7
votes
2
answers
216
views
Choose non-adjacent numbers from intervals
Given a list of intervals with integral endpoints, we want to find out if we can choose one integer from each interval so that no two chosen numbers are adjacent. Can we do this in polynomial time?
My ...
- 131
0
votes
0
answers
89
views
Using Hashing to count the number of occurrences of a pattern within an integer array
So I have a problem that is ,I have an integer array and first I define an interval as a good interval iff, within the interval every integer appears an even (including zero) number of times. I want ...
0
votes
0
answers
146
views
Weighted interval scheduling, exponential time/ NP-complete?
According to this, a weighted schedule is considered NP-complete (not solve-able in polynomial time) if it has groups of 3 or more intervals:
https://en.wikipedia.org/wiki/Interval_scheduling#NP-...
- 11
0
votes
3
answers
2k
views
Greedy algorithm for postive interval covering
Consider the following problem from Jeff Erickson: Algorithms
that also appears in this post, which wants us to prove a lower bound for the problem.
Suppose you are given an array $A[1 .. n]$ of ...
- 267
1
vote
0
answers
26
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:
...
3
votes
1
answer
396
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 ...
- 159
1
vote
2
answers
114
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
82
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
1
vote
1
answer
234
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. ...
- 135
1
vote
0
answers
55
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
470
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
92
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$ ...
- 165
1
vote
0
answers
32
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
941
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 ...
- 593
4
votes
0
answers
116
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
166
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,730
1
vote
0
answers
27
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
171
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 ...
- 63
8
votes
1
answer
389
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 ...
- 12.5k
1
vote
1
answer
1k
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
41
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
113
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
391
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.♦
- 156k
1
vote
1
answer
247
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
242
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
185
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
1k
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
301
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
353
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 ...
- 149
1
vote
0
answers
177
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
119
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
0
votes
1
answer
105
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 ...
- 111
2
votes
1
answer
76
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
80
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
175
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
972
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
433
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
86
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
69
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
63
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
170
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
335
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 ...
