Question: I've got an algorithmic problem that I've not been able to solve. Would appreciate any help with this The main problem: Two laser beams, blue and red color, are shot into a mirror and bounces around. Find the number of intersections between them. Example: red = [2, 7, 8, 15, 20] blue = [3, 4, 5, 7, 10, 16, 21] Should give me 7   red = [10, 20, 30] blue = [1, 10, 20] Should give me 3   My attempt and issue I've been able to solve the second example by setting up pairs of start and end, and checking for each iteration. But this won't work for the first example, as there are 2 intersections between red = [2] and blue = [3]. I circled this part in the picture. Any suggestion on what I should do would be appreciated. Code def count_intersections(red, blue): intersections = 0 # 0 as the starting point red_points = [0] + red blue_points = [0] + blue # Create intervals for red beam red_intervals = [] for i in range(len(red_points) - 1): if i % 2 == 0: red_intervals.append((red_points[i], red_points[i + 1], "Top")) else: red_intervals.append((red_points[i], red_points[i + 1], "Bottom")) # Create intervals for blue beam blue_intervals = [] for i in range(len(blue_points) - 1): if i % 2 == 0: blue_intervals.append((blue_points[i], blue_points[i + 1], "Top")) else: blue_intervals.append((blue_points[i], blue_points[i + 1], "Bottom")) # Check all red intervals against all blue intervals for r_start, r_end, r_start_pos in red_intervals: for b_start, b_end, b_start_pos in blue_intervals: # Check if the intervals overlap and the paths cross if (r_start <= b_start and r_end >= b_end) or (r_start >= b_start and r_end <= b_end): print("check intersects") print(r_start, r_end) print(b_start, b_end) print("next") intersections += 1 return intersections red = [2, 7, 8, 15, 20] blue = [3, 4, 5, 7, 10, 16, 21] # red = [10, 20, 30] # blue = [1, 10, 20] # [(0, 10), (10, 20), (20, 30)] # [(0, 1), (1, 10), (10, 20)] print(count_intersections(red, blue))  Thanks.

Answer: The applicable technique is called a sweep line algorithm. Imagine a vertical line moving from left to right, and consider every "point of interest" at which you get new relevant information. You only need to process the situations at the points of interest, and there are relatively few of those. For your problem, the points of interest are just the bounce points, because everything that happens between them is predictable. To solve it, just check which laser is higher at every bounce point. Let cmp = 1 if red is higher than blue, cmp=-1 if blue is higher than red, or cmp=0 if they're the same. Then you just add 1 intersection to the count every time cmp transitions 1 -> 0, 1 -> -1, -1 -> 0 or -1 -> 1. The code is super easy: def count_intersections(red, blue): redh = 1 # red starts at the top blueh = 1 # blue starts at the top cmp = 0 # They are equal height intersections = 1 # That counts as an intersection redpos = 0 bluepos = 0 while redpos < len(red) and bluepos < len(blue): oldcmp = cmp if red[redpos] == blue[bluepos]: # simultaneous bounce redpos += 1 bluepos += 1 redh = -redh blueh = -blueh cmp = (redh - blueh) // 2 elif red[redpos] < blue[bluepos]: # red bounce first redpos += 1 redh = -redh cmp = redh else: # blue bounce first bluepos += 1 blueh = -blueh cmp = -blueh if cmp != oldcmp and oldcmp != 0: intersections += 1 return intersections red = [2, 7, 8, 15, 20] blue = [3, 4, 5, 7, 10, 16, 21] print(count_intersections(red,blue)) # 7 red = [10, 20, 30] blue = [1, 10, 20] print(count_intersections(red,blue)) # 3