Tuesday, June 27, 2017

Find the common vacant meeting slot

Problem:
Given the meeting slots of several persons, find the common vacant slot in which all the persons can meet.

Input and Output format:
The first line of input contains a single integer n denoting the number of persons. Next n lines of input contain the start and end time of meetings of each person in HH:MM format separated by a space character.

The first line of output should contain the number of distinct vacant slots followed by those many lines containing the start and end time of each vacant slot in HH:MM format separated by a space character.

Sample Input:
4
08:30 09:00
08:45 09:30
09:00 09:30
10:00 11:00

Sample Output:
3
00:00 08:30
09:30 10:00
11:00 23:59

Java Program:
 
package com.sourabh.first;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class CommonMeeting {
    public static void main(String[] args) {
        int A[] = new int[86401];
        Scanner scanner = new Scanner(System.in);
        int persons = Integer.parseInt(scanner.nextLine());
        List<Integer> meetingStartHour = new ArrayList<>();
        List<Integer> meetingStartMinute = new ArrayList<>();
        List<Integer> meetingStartSecond = new ArrayList<>();
        List<Integer> meetingEndHour = new ArrayList<>();
        List<Integer> meetingEndMinute = new ArrayList<>();
        List<Integer> meetingEndSecond = new ArrayList<>();
        
        List<Integer> vacantStartHour = new ArrayList<>();
        List<Integer> vacantStartMinute = new ArrayList<>();
        List<Integer> vacantStartSecond = new ArrayList<>();
        List<Integer> vacantEndHour = new ArrayList<>();
        List<Integer> vacantEndMinute = new ArrayList<>();
        List<Integer> vacantEndSecond = new ArrayList<>();
        
        for(int i=0;i<persons;i++)
        {
            String meeting = scanner.nextLine();
            //System.out.println(meeting);
            String[] parts = meeting.split(" ");
            String[] start = parts[0].split(":");
            String[] end = parts[1].split(":");
            
            meetingStartHour.add(Integer.parseInt(start[0]));
            meetingStartMinute.add(Integer.parseInt(start[1]));
            meetingStartSecond.add(Integer.parseInt(start[2]));
            
            meetingEndHour.add(Integer.parseInt(end[0]));
            meetingEndMinute.add(Integer.parseInt(end[1]));
            meetingEndSecond.add(Integer.parseInt(end[2]));
        }
        
        for(int i=0;i<persons;i++)
        {
            for(int j = 3600 * meetingStartHour.get(i) 
                        + 60 * meetingStartMinute.get(i)
                        + meetingStartSecond.get(i);
                    j <= 3600 * meetingEndHour.get(i) 
                        + 60 * meetingEndMinute.get(i)
                        + meetingEndSecond.get(i);
                    j++) {
                A[j]=1;
            }
        }
        if(A[0] == 0)
        {
            vacantStartHour.add(0);
            vacantStartMinute.add(0);
            vacantStartSecond.add(0);
        }
        for(int i=0;i<86400;i++)
        {
            if(A[i]==1 && A[i+1]==0)
            {
                vacantStartHour.add(i/3600);
                vacantStartMinute.add((i%3600)/60);
                vacantStartSecond.add(i%60);
            }
            else if(A[i]==0 && A[i+1]==1)
            {
                vacantEndHour.add(i/3600);
                vacantEndMinute.add((i%3600)/60);
                vacantEndSecond.add(i%60);
            }
        }
        if(A[86399] == 0)
        {
            vacantEndHour.add(86399/3600);
            vacantEndMinute.add((86399%3600)/60);
            vacantEndSecond.add(59);
        }
        System.out.println(vacantStartHour.size());
        for(int i=0;i<vacantStartHour.size();i++)
        {
            String vacantSlotStart = format(vacantStartHour.get(i)) + ":" +
                                     format(vacantStartMinute.get(i)) + ":" +
                                     format(vacantStartSecond.get(i));
            String vacantSlotEnd = format(vacantEndHour.get(i)) + ":" +
                                   format(vacantEndMinute.get(i)) + ":" +
                                   format(vacantEndSecond.get(i));
            System.out.println(vacantSlotStart + " " + vacantSlotEnd);
        }
    }
    
    private static String format(Integer time) {
        if(time < 10) {
            return "0" + time;
        }
        else {
            return time.toString();
        }
    }
}

2 comments: