- 2020-07-30 03:13
*views 4*- Interview questions / Classical method

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

- Java391 articles
- Python205 articles
- Linux110 articles
- Vue95 articles
- MySQL83 articles
- SpringBoot70 articles
- javascript65 articles
- Spring62 articles
- more...

Daily Recommendation

views 2

©2019-2020 Toolsou All rights reserved,

VUE+Canvas Achieve desktop Pinball brick elimination games C/C++ Memory model 2019PHP Interview questions （ Continuously updated ）PHPspringboot2 Separation of front and rear platforms ,token Put in header Pit for verification Vue SpringBoot conduct Excel download element-ui Step on pit record 45 The 12-year-old programmer was turned down , Is the workplace wrong ?Python Web frame Pandas Fundamentals of statistical analysis _ data processing （DataFrame Common operations ）Java Misunderstanding —— Method overloading is a manifestation of polymorphism ?