What’s the most efficient way to test if two ranges overlap?

by

What does it mean for the ranges to overlap? It means there exists some number C which is in both ranges, i.e.

x1 <= C <= x2

and

y1 <= C <= y2

To avoid confusion, considering the ranges are:
[x1:x2] and [y1:y2]

Now, if we are allowed to assume that the ranges are well-formed (so that x1 <= x2 and y1 <= y2) then it is sufficient to test

x1 <= y2 && y1 <= x2

OR

(StartA <= EndB) and (EndA >= StartB)

More Related Contents:

  1. Why is “1000000000000000 in range(1000000000000001)” so fast in Python 3?
  2. What is the best way to set a register to zero in x86 assembly: xor, mov or and?
  3. Enhanced REP MOVSB for memcpy
  4. Why is Skylake so much better than Broadwell-E for single-threaded memory throughput?
  5. Efficiently compute pairwise squared Euclidean distance in Matlab
  6. Understanding the impact of lfence on a loop with two long dependency chains, for increasing lengths
  7. How to speed up A* algorithm at large spatial scales?
  8. What happens after a L2 TLB miss?
  9. What does gcc’s ffast-math actually do?
  10. Are there any modern CPUs where a cached byte store is actually slower than a word store?
  11. Execute Hive Query with IN clause parameters in parallel
  12. Non-temporal loads and the hardware prefetcher, do they work together?
  13. What is the overhead of Rust’s Option type?
  14. Why is reshape so fast? (Spoiler: Copy-on-Write)
  15. JMeter : How to record HTTPS traffic?
  16. Which loop is faster, while or for?
  17. bsxfun implementation in matrix multiplication
  18. Why is the final reduce step extremely slow in this MapReduce? (HiveQL, HDFS MapReduce)
  19. Unexpectedly poor and weirdly bimodal performance for store loop on Intel Skylake
  20. Why can’t my ultraportable laptop CPU maintain peak performance in HPC
  21. How should I calculate Ramp-up time in Jmeter
  22. How slow (how many cycles) is calculating a square root?
  23. Performance optimisations of x86-64 assembly – Alignment and branch prediction
  24. How are cache memories shared in multicore Intel CPUs?
  25. Ways to improve git status performance
  26. why is data structure alignment important for performance?
  27. Return address prediction stack buffer vs stack-stored return address?
  28. When should we use prefetch?
  29. Relative performance of x86 inc vs. add instruction
  30. Efficient sse shuffle mask generation for left-packing byte elements

Leave a Comment