A - Intersection Editorial by en_translator


This problem asks to find the length of the common segment of \([L_1,R_1]\) and \([L_2,R_2]\).

To come to the point, the answer can be found by \(\max(0,\min(r1,r2)-\max(l1,l2))\), which directly leads you to the implementation.

We explain how to solve the problem without the knowledge.

This problem is troublesome because there are various possibilities of which value is greater than others. Specifically, there are \(6\) cases:

  • \(L_1\leq R_1\leq L_2\leq R_2\)
  • \(L_1\leq L_2\leq R_1\leq R_2\)
  • \(L_1\leq L_2\leq R_2\leq R_1\)
  • \(L_2\leq L_1\leq R_1\leq R_2\)
  • \(L_2\leq L_1\leq R_2\leq R_1\)
  • \(L_2\leq R_2\leq L_1\leq R_1\)

If it belongs to multiple cases, you may classify it to any of them. First, if \(L_1>L_2\), then we can swap \((L_1,R_1)\) and \((L_2,R_2)\), so that the cases are limited to the following three, with the corresponding answers:

  • \(L_1\leq R_1\leq L_2\leq R_2\) \(\to\) \(0\)
  • \(L_1\leq L_2\leq R_1\leq R_2\) \(\to\) \(R_1-L_2\)
  • \(L_1\leq L_2\leq R_2\leq R_1\) \(\to\) \(R_2-L_2\)

All that left is to implement it with a if statement.

Therefore, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main() {
	int l1, r1, l2, r2;
	cin >> l1 >> r1 >> l2 >> r2;
	if (l1 > l2) {
		swap(l1, l2);
		swap(r1, r2);
	}
	if (r1 <= l2)cout << 0 << endl;
	else if (r1 <= r2)cout << r1 - l2 << endl;
	else cout << r2 - l2 << endl;
        // cout << max(0, min(r1, r2) - max(l1, l2)) << endl; (this is sufficient in fact)
	return 0;
}
// 

Sample code in Python:

l1,r1,l2,r2 = map(int, input().split())
if(l1>l2):
    l1,r1,l2,r2=l2,r2,l1,r1
if(r1<=l2):
    print(0)
elif(r1<=r2):
    print(r1-l2)
else:
    print(r2-l2)

posted:
last update: