Find closest non-overlapping ranges from start to end

Question

I would like to find the closest ranges that do not overlap from the first start to the last end position. Any idea how to proceed? In the example below c(8, 33) and c(155, 161) should be filtered out because they overlap with the preceding range.

#Example data
df <- data.frame(
  start = c(7,8,14,34,67,92,125,155,170,200),
  end = c(13,33,25,66,91,124,155,161,181,214)
)

   start end
1      7  13
2      8  33
3     14  25
4     34  66
5     67  91
6     92 124
7    125 155
8    155 161
9    170 181
10   200 214

#Overlapping rows
  start end
1     8  33
2   155 161

#Desired output where overlapping rows are filtered away
  start end
1     7  13
2    14  25
3    34  66
4    67  91
5    92 124
6   125 155
7   170 181
8   200 214

Row 3, 14 25 overlaps with row 2 8, 33 but it is not removed? — Ronak Shah, Sep 07 '20 at 08:04

score 2 · Answer 1 · answered Sep 07 '20 at 08:05

I would do this as a simple loop, since whether a row is excluded depends on the result of the calculation for the previous row

i <- 2

while(i < nrow(df)) {
  if(df$start[i] <= df$end[i - 1]) {
    df <- df[-i,] 
  } else { 
    i <- i + 1
  }
}

df
#>    start end
#> 1      7  13
#> 3     14  25
#> 4     34  66
#> 5     67  91
#> 6     92 124
#> 7    125 155
#> 9    170 181
#> 10   200 214

ThomasIsCoding · Answer 2 · 2020-09-08T08:55:50.907

0

Since your start column has been in the ascending order, you can check the overlap via the values of end only, e.g.,

repeat {
  ind <- with(df, head(which(!c(TRUE,end[-nrow(df)]<start[-1])),1))
  if (!length(ind)) break
  df <- df[-ind,]
}

which gives

> df
   start end
1      7  13
3     14  25
4     34  66
5     67  91
6     92 124
7    125 155
9    170 181
10   200 214

edited Sep 08 '20 at 08:55

answered Sep 07 '20 at 10:41

ThomasIsCoding

96,636
9
24
81

very nice but it would not work for the following sequence: df <- data.frame(start = c(7,8,100), end = c(8,100,101)) – Nivel Sep 07 '20 at 11:16
@Nivel Then what's your desired output? – ThomasIsCoding Sep 07 '20 at 11:24
The desired output would be start = c(7, 100), end = c(8, 101). If I use your formula also the last row is dropped. – Nivel Sep 07 '20 at 11:44
@Nivel It seems you keep the last row anyway. Please check out my update – ThomasIsCoding Sep 07 '20 at 12:29
Sorry but it still doesn't produce the correct output. Consider the following: df <- data.frame(start = c(7,8,10,12,14), end = c(16,9,11,13,15)). The desired output is start = 7 and end = 16. – Nivel Sep 08 '20 at 08:16
@Nivel I am a bit confused. Why the row 3 in your example is kept even it is overlapped with row 2? – ThomasIsCoding Sep 08 '20 at 08:25

score 0 · Answer 3 · answered Sep 08 '20 at 08:19

I went with the following answer posted on the R community website:

find_nonover <- function(df) {
  to_drop <- logical(nrow(df))
  for (i in seq_along(df[["end"]])) {
    if (i %in% which(to_drop)) next
    to_drop <- to_drop | c(logical(i), df[i, "end"] >= df[["start"]][-seq_len(i)])
  }
  list(nonover = df[!to_drop, ],
       over    = df[to_drop, ])
}

https://community.rstudio.com/t/find-closest-non-overlapping-ranges-from-start-to-end/79642/3

Find closest non-overlapping ranges from start to end

3 Answers3