Problem description :

There is a straight line , From origin to infinity .

There are on this line N Line segments . Line segments may intersect .

ask ,N How long are the lines covered in total ?( Areas covered repeatedly are calculated only once )

================================================

Thinking of problem solving :

You can split each segment into “ Company 1”

Traverse all segments , Use an array to record what each line segment passes through “ Company 1”

Finally, count the passed in the array “ Company 1” The number of , This is the total length covered by all segments .

There's a problem here ? How to determine the size of an array ?

The size of the array should be the largest endpoint coordinate of all segments .

 ===============================================

By the way, I have a question .

Several line segments are given . How many, please “ Connected domain ”. It's the line segments that will be able to merge Merge into one line segment .

Finally, several can be merged ?

Use the ideas above . It's simple .

Just make a start and end record when traversing the unit array .

The program is implemented as follows .

===============================================
// Requirements for this question // Find out the length of the whole line covered by all the line segments . // The overlap is calculated only once .
//================================ // The idea of this algorithm is , Pixel each line segment , // Add to an array of units c[N] in
// ergodic c Array to determine which units are covered , // stay count Count it and you'll know how many miles it covers . // How clever .
//============================== #include <iostream> using namespace std; const
int N = 10000; // Segment structure struct Segment { int start; int end; }; // int
coverage(Segment *segments, int n) { bool c[N]={false};// each “ Company 1” Is it covered int
start=0; int end = 0; // ergodic n Line segments for(int i = 0; i < n; i++) { for(int j =
segments[i].start; j < segments[i].end; j++) { c[j] = true; } // Look for the rightmost end
if(segments[i].end > end) { end = segments[i].end; } // Look for the far left
if(segments[i].start < start) { start = segments[i].start; } }
// From the far left to the right . Traversing unit array C int count = 0; for(int i= start; i < end; i++) { if(c[i])
{ int s=i; while(c[i]) { count++; i++; } int e=i; cout <<
"["<<s<<","<<e<<"]"<<endl; } } return count; }; int main() { Segment s1;
s1.start = 1; s1.end = 3; Segment s2; s2.start = 2; s2.end = 6; Segment s3;
s3.start = 11; s3.end = 12; Segment s4; s4.start = 10; s4.end = 13; Segment
ss[] = {s1,s2,s3,s4}; cout << " After merger "<<endl; cout <<" Total length covered :" <<coverage(ss,
sizeof(ss)/sizeof(ss[0]))<<endl; }
The output results are as follows :

After merger
[1,6]
[10,13]

Total length covered
8

Please press any key to continue . .

 

 

Technology
©2019-2020 Toolsou All rights reserved,
Digital rolling lottery program Keras Save and load model (JSON+HDF5) Remember once EventBus Project issues caused by memory leaks I've been drinking soft water for three years ? What is the use of soft water and water softener msf Generate Trojan horse attack android mobile phone Time conversion front desk will 2020-07-17T03:07:02.000+0000 Into 2020-07-17 11:07:02 Chuan Shen 1190 Reverses the substring between each pair of parentheses leetcodehive Summary of processing methods for a large number of small files SparkSQL Achieve partition overlay write Image format conversion