Questions tagged [intervals]
The intervals tag has no summary.
126 questions
0 votes
1 answer
59 views
Finding the top N elements from a subset of a Minkowski sum of two sets of disjoint time intervals that have minimal overlap with a given interval set
We have two sets A and B, where each element in A and B is a set of disjoint time intervals We have a set C which is a subset of the Minkowski sum A + B, meaning: For any a ∈ A and b ∈ B, if a + b ∈ ...
- 19
1 vote
1 answer
73 views
Complexity of determining feasibilty of a generalization of the interval scheduling problem
Consider the following generalization of the interval scheduling problem: We have a set of groups, each group is specified by a set of disjoint time intervals. Unlike the group interval scheduling ...
- 19
0 votes
1 answer
140 views
Efficiently Merging Sorted (Key, Value) Lists
I'm working with multiple ordered lists, each containing tuples of the form (key, value), where each list is sorted in ascending order by ...
- 75
1 vote
1 answer
77 views
Finding the minimum cost at each point in time from a set of weighted intervals
Lets say we have a list of intervals that also has a value associated with it. Assume that there is always atleast on interval active. The solution would be a timeline of non overlapping intervals ...
- 75
1 vote
0 answers
168 views
Fast data structure for disjoint intervals
Over the years I've worked on a few applications that needed to model time intervals that are disjoint. For example, there's some kind of equipment available and time slots are booked out. For a data ...
- 61
3 votes
1 answer
130 views
Cover a set of points using subintervals of a list of intervals
Given a set of points $\{p_1, p_2, \dots p_n\}$ and a set of intervals $I =\{[a_1, b_1], \dots [a_m, b_m]\}$, you are asked to find a set of subintervals $S = \{[c_1, d_1], \dots [c_m, d_m]\}$ where $[...
- 161
3 votes
3 answers
212 views
Detect if an interval is fully covered by union of previous intervals in sequence
Given a sequence of intervals $I_1, I_2, \ldots$, is there an efficient way to detect whether some interval $I_i$ is completely contained in the union of the preceding intervals $I_1, \ldots, I_{i-1}$?...
- 163
2 votes
1 answer
446 views
Minimum number of intervals from a set to cover all intervals of another set
There are two sets of intervals provided to us. target = {{11,13}, {7,10}, {0,3}, {6,6}} space = {{10,12}, {2,6}, {4,8}, {0,4}, {9,10}} I need to find the minimum number of intervals I can pick from ...
- 23
0 votes
1 answer
84 views
Optimizing Pairings Between Integers and Intervals for Maximal Matching
Consider the scenario where we are given a collection of n integers. These integers are unordered and may include duplicates. Additionally, we have a set of m ranges, each defined by two integers ...
2 votes
2 answers
143 views
Turning stacked overlapping intervals (with associated data) into non-overlapping intervals
I'm looking for an efficient algorithm to merge a list of overlapping intervals (each of which has data associated) into non-overlapping intervals. In case two or more intervals overlap, the latter ...
- 226
1 vote
1 answer
351 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
83 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 ...
- 13
2 votes
0 answers
151 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 ...
- 21
-2 votes
2 answers
164 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
89 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 ...
