Question :
STATEMENT
There are n events. Each has a start time and end time. You wish to attend maximum of such events.
NOTE:If start time of one event is same as end time of other you cannot attend both. You can imagine some time to travel from event1 to event2.
INPUT
The first line will contain an integer T, denoting the number of test cases.
Each test case contains several lines.
The first line of each test case will contain an integer N, denoting the number of events.
The next N lines, one for each event, contain two space separated integers, starttime and endtime.
1 <= T <= 10
1 <= N <= 10000
0 <= starttime < endtime <= 1000000000
OUTPUT
For each test case, output a single integer denoting the maximal number of events that you can attend.
EXAMPLE
INPUT
2
5
0 5
0 2
3 5
3 4
5 6
6
0 8
8 10
11 12
11 15
2 5
7 9
OUTPUT
3
3
EXPLANATION
In the first case you can attend events (0, 2), (3, 4), (5, 6)
Solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
/**
*
* @author athakur
*
*/
public class Quark1 {
public static void main(String args[]) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(System.out,true);
int noOfTestCases = Integer.parseInt(reader.readLine());
for(int i=0; i<noOfTestCases; i++) {
int noOfEvents = Integer.parseInt(reader.readLine());
Event[] events = new Event[noOfEvents];
for(int j=0; j< noOfEvents; j++) {
String[] times = reader.readLine().split(" ");
events[j] = new Event(Integer.parseInt(times[0]),Integer.parseInt(times[1]));
}
writer.println(getMaxEvents(events));
}
}
private static int getMaxEvents(Event[] events) {
Arrays.sort(events);
int i=0;
int count = 1;
for (int j=1; j<events.length;j++) {
if(events[j].startTime > events[i].endTime) {
count++;
i=j;
}
}
return count;
}
static class Event implements Comparable<Event>
{
int startTime;
int endTime;
public Event(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
@Override
public int compareTo(Event event) {
return this.endTime > event.endTime ? 1 : (this.endTime < event.endTime ? -1 : 0);
}
}
}
Explanation :
First we sort the events based on the finish time because we want to attend earliest events first. Now if end times if two events are same we can attend either. So we don't bother about it. On sorting such events can have sequential positioning (one after the other) in either way. Next we start from first event in sorted events list. We can only attend next event if it's start time is greater (mind even equals will not work as we have to consider commute delay) than the end time of current event. Current event is tracked with i variable where as next event is tracked with j.
