Questions tagged [intervals]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
29 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 ...
jack norton's user avatar
2 votes
2 answers
61 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 ...
Johannes Weiss's user avatar
1 vote
1 answer
96 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 ...
guitarMan's user avatar
0 votes
0 answers
24 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 ...
SotirisD's user avatar
2 votes
0 answers
119 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 ...
quTANum's user avatar
  • 21
-1 votes
2 answers
75 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 ...
John's user avatar
  • 1
0 votes
1 answer
35 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 ...
Soroush Vahidi's user avatar
0 votes
1 answer
483 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 ...
Tejas Anand's user avatar
2 votes
2 answers
814 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 ...
Kitwradr's user avatar
  • 123
1 vote
1 answer
130 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. ...
JohnHernandez's user avatar
7 votes
2 answers
222 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 ...
simmons's user avatar
  • 131
0 votes
0 answers
100 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 ...
ISeekTheWisdom's user avatar
0 votes
0 answers
207 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-...
Tyler's user avatar
  • 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 ...
ErroR's user avatar
  • 1,910
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: ...
Alexandr Dorofeev's user avatar
3 votes
1 answer
478 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 ...
NiRvanA's user avatar
  • 159
1 vote
2 answers
127 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 ...
chrylis -cautiouslyoptimistic-'s user avatar
3 votes
1 answer
85 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 ...
worldsmithhelper's user avatar
1 vote
1 answer
257 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. ...
Vectorizer's user avatar
1 vote
0 answers
68 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 ...
Th F's user avatar
  • 11
0 votes
1 answer
497 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 ...
Dincio's user avatar
  • 111
3 votes
1 answer
101 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$ ...
Sid's user avatar
  • 165
1 vote
0 answers
33 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 ...
IUissopretty's user avatar
5 votes
1 answer
2k 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 ...
AspiringMat's user avatar
4 votes
0 answers
128 views

Efficient 2d interval merging product

Suppose I have two tables of 2d intervals (axis-aligned rectangles) with values attributed to each interval. ...
yupbank's user avatar
  • 215
7 votes
0 answers
170 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$...
Erel Segal-Halevi's user avatar
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 ...
nick2225's user avatar
  • 111
3 votes
1 answer
176 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 ...
df21's user avatar
  • 63
8 votes
1 answer
427 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 ...
Nathaniel's user avatar
  • 15.6k
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 ...
Karambit's user avatar
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: ...
Luca Spiller's user avatar
1 vote
1 answer
123 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 ...
Nate S.'s user avatar
  • 11
3 votes
2 answers
464 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.'s user avatar
  • 159k
1 vote
1 answer
294 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 ...
Elliott de Launay's user avatar
2 votes
1 answer
271 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? ...
pblpbl's user avatar
  • 43
1 vote
1 answer
208 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 ...
Sebastian Allard's user avatar
2 votes
2 answers
2k 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 ...
Mojo's user avatar
  • 123
0 votes
1 answer
335 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 ...
andrewz's user avatar
  • 103
4 votes
1 answer
373 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 ...
mibm's user avatar
  • 149
1 vote
0 answers
205 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 ...
ThundeRat's user avatar
2 votes
1 answer
120 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 ...
sn0wtroopeer's user avatar
0 votes
1 answer
127 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 ...
milck's user avatar
  • 111
2 votes
1 answer
82 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)...
DoubtExpert's user avatar
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 ...
user119447's user avatar
2 votes
1 answer
191 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 ...
cena1's user avatar
  • 21
2 votes
2 answers
1k 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. ...
taktoa's user avatar
  • 364
9 votes
1 answer
451 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{...
taktoa's user avatar
  • 364
2 votes
1 answer
88 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 ...
taktoa's user avatar
  • 364
3 votes
1 answer
70 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 ...
dysonsfrog's user avatar
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 ...
greedoid228's user avatar