SRM 730, D2, 250-Pointer (IntervalIntersections)

James S. Plank

Thu Aug 30 23:50:20 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: February, 2018
Competitors who opened the problem: 267
Competitors who submitted a solution: 236
Number of correct solutions: 178
Accuracy (percentage correct vs those who opened): 66.7%
Average Correct Time: 16:04

You are given two intervals [x₁,y₁] [x₂,y₂]. Do yourself a favor and relabel the intervals -- make them [x_first,y_first] and [x_second,y_second], such that you know that x_first ≤ x_second. In example 0, [x_first,y_first] = [1,2] and [x_second,y_second] = [3,6]. Same for example 1. Doing this makes it easier to reason about the solution.

There are only two choices now -- either (x_first,y_first) and (x_second,y_second) intersect each other, in which case you'll return 0, or they don't, in which case you'll return x_second-y_first.

It is really that simple, and relabeling the intervals helps to make it that simple.