#K69777. Minimum Temperature Zones
Minimum Temperature Zones
Minimum Temperature Zones
You are given n types of plants. For each plant type, you are provided with a pair of integers \(L\) and \(H\) representing the lowest and highest temperatures at which the plant can grow. Your task is to determine the minimum number of temperature zones required such that each zone is defined by a fixed temperature, and every plant type can be assigned to a zone where its temperature range covers that fixed temperature.
Note: A single temperature zone can serve multiple plant types if the fixed temperature lies within their respective temperature ranges. Use a greedy algorithm approach by considering the ranges sorted by their upper bounds.
Input/Output method: All input is given from stdin
and output should be printed to stdout
.
inputFormat
The first line contains an integer n representing the number of plant types. Each of the following n lines contains two space-separated integers \(L\) and \(H\) indicating the minimum and maximum temperature for the plant type.
For example:
3 15 20 18 25 23 30
outputFormat
Output a single integer representing the minimum number of temperature zones required so that each plant type is assigned a zone with a temperature within its range.
## sample1
5 10
1
</p>