SnowyWinter
SRM 391 · 2008-02-26 · by stone
SRM 391 · 2008-02-26 · by stone · Brute Force, Sorting
Problem Statement
Problem Statement
Southern China is suffering from a heavily snowy winter. The heavy snow even causes the closure of an important highway connecting southern and northern China. You've got several reports containing the start and end points of highway segments covered by heavy snow. Given those reports as two int[] s startPoints and endPoints, you are to return the total length of highway segments covered by snow. Note that the reported segments may overlap.
Constraints
- startPoints will contain between 1 and 50 elements, inclusive.
- endPoints will contain the same number of elements as startPoints.
- Each element of startPoints and endPoints will be between 0 and 10000, inclusive.
- The i-th element of startPoints will be smaller than the corresponding element in endPoints.
Examples
0)
{17,85,57}
{33,86,84}
Returns: 44
These segments don't overlap.
1)
{45,100,125,10,15,35,30,9}
{46,200,175,20,25,45,40,10}
Returns: 132
There are 3 segments covered by snow: 9-25, 30-46 and 100-200.
2)
{4387,711,2510,1001,4687,3400,5254,584,284,1423,3755,929,2154,5719,1326,2368,554}
{7890,5075,2600,6867,7860,9789,6422,5002,4180,7086,8615,9832,4169,7188,9975,8690,1423}
Returns: 9691
The snow covered segment is 284-9975.
3)
{4906,5601,5087,1020,4362,2657,6257,5509,5107,5315,277,6801,2136,2921,5233,5082,497,8250,3956,5720}
{4930,9130,9366,2322,4687,4848,8856,6302,5496,5438,829,9053,4233,4119,9781,8034,3956,9939,4908,5928}
Returns: 9510
There are 2 segments covered by snow: 277-4930 and 5082-9939.
4)
{0,4,2}
{1,5,3}
Returns: 3
21)
{4387,711,2510,1001,4687,3400,5254,584,284,1423,3755,929,2154,5719,1326,2368,554}
{7890,5075,2600,6867,7860,9789,6422,5002,4180,7086,8615,9832,4169,7188,9975,8690,1423}
Returns: 9691
The snow covered segment is 284-9975.
Submissions are judged against all 72 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SnowyWinter with a public method int snowyHighwayLength(vector<int> startPoints, vector<int> endPoints) · 72 test cases · 2 s / 256 MB per case