Questions tagged [interval-intersection]
11 questions
24
votes
10 answers
A range intersection algorithm better than O(n)?
Range intersection is a simple, but non-trivial problem.
Its has been answered twice already:
Find number range intersection
Comparing date ranges
The first solutions is O(n) and the second solution is for a database (which is less than O(n) of…
Pyrolistical
- 27,624
- 21
- 81
- 106
4
votes
1 answer
Detecting overlapping date recurrence rules
I'm working in a application that looks like Google Calendar, but with one main difference: events shouldn't have intersections with other events. This means that no two events may share common time, even in minutes granularity. This is specially…
fjsj
- 10,995
- 11
- 41
- 57
4
votes
1 answer
Intersecting ranges of consecutive values in logical vectors in R
I have two logical vectors which look like this:
x = c(0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0)
y = c(0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0)
I would like to count the intersections between ranges of consecutive values. Meaning that consecutive values…
Cos
- 1,649
- 1
- 27
- 50
3
votes
2 answers
Intervalindex merging in Pandas through duplicate dates + uniqueID
First question in SO, still learning python & pandas
EDIT: I've successfully pivoted the values DF to go from long to wide in order to have unique id+date indices (e.g. no uniqueID has more than 1 row per day). However, I've stil not been able to…
cjcrm
- 89
- 8
3
votes
3 answers
Similarity of two sets of intervals
What sort of algorithm/solution could be used to indicate the similarity (overlap/precision/recall/...) of two sets of ranges.
I can think of (or find online) hundreds of similar problems but never exact, but surely this "wheel" must have been…
user7048002
1
vote
1 answer
How to find interval overlaps between two lists, if intervals in the same list can overlap
I have a list of intervals in lists A,B
I need to find which intervals overlap between A,B
I am trying to find a better method than the brute-force one which has time complexity O(len(A)*len(B)) cause I am working with pretty large lists.
The best…
dimitris_ioan
- 11
- 1
1
vote
3 answers
Algorithm to reduce one time frame by another time frame
We have a time frame general_availability (marked as grey in the image below) that overlaps with a time frame time_off (marked as yellow in the image below). This overlap can take any shape as shown in the image below.
What's the algorithm to create…
migu
- 4,236
- 5
- 39
- 60
1
vote
1 answer
Overlapping radial intervals, python
Suppose I have some intervals, in radian, which represent angular sectors on a circle.
The first number is the beginning of the interval, the second number is the end of the interval. Both numbers are connected in counter-clockwise direction, i.e…
Mathusalem
- 837
- 9
- 21
1
vote
3 answers
Interval intersection
I wrote a class that checks whether two integer intevals overlap.
However I don't like this solution to much. I think that it's possible to do it in a better and simpler way.
public class IntegerInterval implements Interval {
private Integer…
BlueLettuce16
- 2,013
- 4
- 20
- 31
0
votes
2 answers
Counting intersections per run of 1s in the first of two logical vectors
A more general version of this question has been answered here. A user proposed I ask this more specific version of the question as a separate post.
I have two logical vectors which look like this:
x = c(0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0)
y =…
Cos
- 1,649
- 1
- 27
- 50
0
votes
2 answers
Overlapping time intervals WITHOUT for/while loops
The best way to ask my question is via a clear example. Consider 2 timelines (e.g. time in seconds) A and B where the intervals for each timeline are:
intervals_a =
0 1
1 4
4 7
7 9
intervals_b =
0 2
2 3
3 5
5 8
Notice…
Hamad Al-Sayed
- 3
- 2