The secretary of school
Martha Georgiyivna starts her every working day with pretension to director:
- Here you, Ivan Ivanovych,
already bought the program for scheduling to the deputy from educational part.
And what do I have to do? I need to make the graphic of visitors according to
Your needs in fact. And you didn’t buy the program for work planning for me.
Please try to help secretary
in her work. You have to organize the graphic of the visitors based on their wishes
left in the secretary book.
Receiving two visitors at
the same time is prohibited. When meeting with one visitor is finished, the
meeting with another visitor can start – they can meet at the cabinet door.
Input.
The first line contains the number of visitors n (n ≤ 1000)
who signed up for a meeting. There are two numbers T1i and T2i in each of the next n lines, separated with one space. The meeting with director starts
at T1i, and at T2i the meeting ends. The time
is written in format hh:mm. It is known that n ≤ 1000, time is given
during one day, and T2i ≥ T1i
for all i.
Output. Print the maximum number of visitors, who will be able to have a
meeting with director of school during the working day.
|
Sample input |
Sample output |
|
4 09:10 13:05 14:25 14:30 14:20 15:15 15:00 17:00 |
3 |
SOLUTION
greedy
Convert time to minutes. Ńreate an array of segments – time intervals
[T1i; T2i). Sort them in ascending order of finish time.
Next, greedily
select visitors: iterate over the intervals from left to right and select those intervals that
do not intersect with already selected.
Declare the class
segment,
that will store the time
interval [start; fin).
class segment
{
public:
int start, fin;
segment(int start, int fin) : start(start), fin(fin) {}
};
Store the
set of input intervals in the vector v.
vector<segment> v;
Function
f to sort the segments. The intervals are sorted in ascending
order of their finish time.
int f(segment a, segment b)
{
return a.fin <= b.fin;
}
The main part of the program. Read the input
data.
scanf("%d", &n);
while (n--)
{
scanf("%d:%d %d:%d",
&h1, &m1, &h2, &m2);
Save the
time in intervals in minutes.
v.push_back(segment(h1 * 60 +
m1, h2 * 60 + m2));
}
Sort the
time intervals.
sort(v.begin(),
v.end(), f);
We accept a visitor who has a zero interval (intervals are
numbered from zero). Let the current visitor accepted by director, corresponds to the time
interval cur. Since the director will
always accept a visitor
number zero, set cur = 0. In the variable res we count the number of accepted visitors.
Since director accepts visitor number 0, initialize res = 1.
cur =
0; res = 1;
Iterate
the intervals, starting from i = 1.
for (i = 1; i < v.size(); i++)
{
Look for
an interval, the start of which
is not less than the finish
time of the current one. We accept a visitor from this interval and set
this interval as current.
if (v[i].start >= v[cur].fin)
{
cur = i;
res++;
}
}
Print
the number of accepted visitors.
printf("%d\n", res);
Store the array
of segments in a vector v.
vector<pair<int, int> > v;
Read the
input data. Convert time to minutes. Put the finish time first in a pair, since by default the vector of pairs
is sorted by the first component.
scanf("%d", &n);
while (n--)
{
scanf("%d:%d %d:%d", &h1, &m1,
&h2, &m2);
v.push_back(make_pair(h2
* 60 + m2, h1 * 60 + m1));
}
Sort
the pairs.
sort(v.begin(), v.end());
In the variable res count
the number of selected segments.
i = res = 0;
while (i <
v.size())
{
The end
of the next selected segment store in the variable temp.
res++; temp =
v[i++].first; // end
Look for
the next segment, that
starts no earlier than temp.
while (i < v.size() && v[i].second < temp) i++;
}
Print
the number of accepted visitors.
printf("%d\n", res);
Java realization
import java.util.*;
class Segment
{
int start, fin;
public Segment(int start, int fin)
{
this.start = start;
this.fin = fin;
}
}
public class Main
{
public static class MyFun implements Comparator<Segment>
{
public int
compare(Segment a, Segment b)
{
return a.fin - b.fin;
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
ArrayList<Segment> seg = new
ArrayList<Segment>();
for (int i = 0; i < n; i++)
{
String s = con.next();
StringTokenizer st = new StringTokenizer(s, ":");
int h = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int start = h * 60 + m;
s = con.next();
st = new StringTokenizer(s, ":");
h = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
int fin = h * 60 + m;
seg.add(new Segment(start,fin));
}
Collections.sort(seg, new
MyFun());
int cur = 0, res = 1;
for (int i = 1; i < seg.size(); i++)
{
if (seg.get(i).start >=
seg.get(cur).fin)
{
cur = i;
res++;
}
}
System.out.println(res);
con.close();
}
}