Three Matches
InterviewTime limit1sMemory limit1024 MB
Given three matches on a line, find the minimum number to light so fire spreads to all, and report the shortest and longest lengths.
- Level
Easy2 of 10
- Topics
- Implementation, Sorting, Intervals, Brute force
- Solved
- No attempts yet
Problem
Three matches lie on a straight line. The line is marked with ticks every 1 centimeter. The ticks are numbered with consecutive integers starting from 1. Each match is given by its left end and its right end.
The goal is to set all three matches on fire.
When two matches are next to each other (as the first two matches are in the picture), or they touch (the end of one match is the start of the next), the fire from one will set the other on fire, so it is enough to light only one of them.
The picture shows three matches. To burn all of them, we can light the first and the last match.
Write a program stick that finds the minimum number of matches that must be lit so that all three matches burn.
Input
Three lines of the standard input contain two integers each, giving the left end and the right end of each match. The numbers are separated by a single space.
The matches are ordered by their left end: the first line holds the match that starts leftmost, and so on.
Output
On the first line of the standard output the program must print a single integer, the minimum number of matches that must be lit.
On the second line of the standard output the program must print two integers separated by a single space: the lengths of the shortest and the longest of the three matches.
Constraints
The line is no longer than 100 centimeters.