Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 4 vote

@Phoenix: your output comes from a wrong algorithm, isn't it?

UPDATED:
O(N+M) time algorithm:
- Merge two sorted interval lists into one sorted list, sorted by start time
- Consider the begin of each interval as a time-point;
- For each time-point, keep track of the latest time of any busy period we see so far.
- If this latest time is still before the next time-point, that will be the free period.

Code is quite short:

#include <iostream>
#include <algorithm>
using namespace std;
int N=5;
pair<int,int> Person1[] = { {1,5}, {10, 14}, {19,20}, {21,24}, {27,30} };
int M=4;
pair<int,int> Person2[] = { {3,5}, {12, 15}, {18,21}, {23,24} };

pair<int,int> TimePoints[100];
int C=N+M;

int main()
{
    //merge two sorted lists into a list sorted by start time
    int p1=0, p2=0, k=0;
    while(k<C){
        if (Person1[p1].first <  Person2[p2].first
            ||( Person1[p1].first == Person2[p2].first &&
                Person1[p1].second < Person2[p2].second ))
            TimePoints[k++] = Person1[p1++];
        else
            TimePoints[k++] = Person2[p2++];

        if (p1 >=N) while(p2<M) TimePoints[k++] = Person2[p2++];
        if (p2 >=M) while(p1<N) TimePoints[k++] = Person1[p1++];
    };

    //mark latest time so far and print free period
    int latestSoFar = 0;
    for(int i = 0; i < C-1; i++){
        latestSoFar = max(latestSoFar, TimePoints[i].second);
        if (TimePoints[i+1].first > latestSoFar) // next start time is after the latest
            cout <<latestSoFar<<" "<<TimePoints[i+1].first<<endl;
    }
    return 0;
}

- ninhnnsoc December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I just realized that intervals in the input are sorted.
Thus, we can do in linear time.
My post was updated.

- ninhnnsoc December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The output should be their common free times. Is it not correct?

- Phoenix December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Phoenix, (22,22) is wrong because person 1 has (21,24)

- CT December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I've just came up with exactly same solution as you did. Let's hope it's a correct one :)

- damluar July 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We could also avoid using additional array to store sorted elements,
We can go through elements from both array, increasing either p1 or p2 index and checking if there is a free period directly.
But it will make the solution more difficult to follow.

- damluar July 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can we use a multimap to store all elements by which we can avoid explicitly merging two arrays?

- jp December 05, 2019 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

Here is an untested code, I have combined psedocode and some code to convey the logic..

At a high level try to take out the busy schedule from available dates. That will give you free dates. Once we have common freedates get the interval logic implemented.

struct timeInterval
{
	int upperlimit;
	int lowerlimit;
}


ArrayList PersonTimeIntervales [] = timeInterval 
{
	{1,5}, 
	{10, 14},
	{19,20},
	{21,24},
	{27,30}
}

ArrayList PersonTimeIntervales2 [] = timeInterval 
{
	(3,5), 
	(12,15),
	(18, 21),
	(23, 24) 
}

int []calendarDate = new int[30]
calendarDate = {1,2,    to 30}

Take out the busy dates from common calendarDate  array 
foreach(TimeInterval T in PersonTimeIntervales)
{
	foreach(i=t.lowerbound; i<=t.upperbound; i++)
	{
		calendarDate [i] = 0;
	}
}

foreach(TimeInterval T in PersonTimeIntervales1)
{
	foreach(i=t.lowerbound; i<=t.upperbound; i++)
	{
		// we can add check if need to see if the date is already set to 0
		calendarDate [i] = 0;
	}
}


calendarDate []: 0 0 0 0 0 6 7 8 9 0 0 0 0 0 0 0 16 17 0 0 0 0 0 0 0 0 25 26 0 0 0 0 

tempUpperB = 0 ;
templowerB = 0 ;
for(int i = 1; i<=30; i++)
{
	if (calendarDate [i] > 0)
	{	
		if (templowerB = 0 )
		{
			
			templowerB = calendarDate [i] ; 
		}	
		tempUpperB  =  calendarDate [i] ; 
		continue;
	}
	if (calenderDate[i] = 0)
	{
		if (tempUpperB > 0 )
		{
			freeTime[counter++] = TimeInterval{templowerB, tempUpperB ) ; 	
			tempUpperB = 0
		}
		else
		{
			templowerB = 0
		}
	}
}

- Jai December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Why (22,22) is a free time interval?
per1 is busy in (21,24) range.

def GAP(P1, P2):
    l1 = len(P1)
    l2 = len(P2)
    
    l = min(l1,l2)
    i1=0
    i2=0
    now = 1
   
    while(True):
        
        if(P1[i1][0]<P2[i2][0]):
            start = P1[i1][0]
            end   = P1[i1][1]
            i1 = i1 + 1
            if(start-now)>=1:
                print '(',now,',',start-1,')'
            
            if((P2[i2][0]-end)<=1):
                end = max(end,P2[i2][1])
                i2 = i2 + 1
            
            
        else:
            start = P2[i2][0]
            end   = P2[i2][1]
            i2 = i2 + 1
            if(start-now)>=1:
                print '(',now,',',start-1,')'
            
            if((P1[i1][0]-end)<=1):
                end = max(end,P1[i1][1])
                i1 = i1 + 1
        
        now = end+1
        
        if(max(i1,i2)==l):
            break
        
    
    if(l1==l):
        for i in range(l, l2):
            if((P2[i][0]-now)>=1):
                print '(',now,',',P2[i][0]-1,')'
                
            if(P2[i][1]+1>now):
                now = P2[i][1]+1
    else:
        for i in range(l, l1):
            if((P1[i][0]-now)>=1):
                print '(',now,',',P1[i][0]-1,')'
                
            if(P1[i][1]+1>now):
                now = P1[i][1]+1
            
        
        

A = [(1,5), (10, 14), (19,20), (21,24), (27,30)]
B = [(3,5), (12,15), (18, 21), (23, 24)]

GAP(A,B)

- Aerofoil.kite December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 6 vote

EDIT: Handle any number of people by arranging their range iterators into a heap. This reorganization also improves readability of the algorithm logic.

static class Range {
		int B;
		int E;
		Range ( int b, int e) {
			B=b;
			E=e;
		}
		public String toString() { return "("+B+","+E+")";}
	}	
	
	public static List<Range> findFreeRanges
			(int start, int end, List<Range> ... schedules) {
		
		int beginCounter = 0;
		int next = 0;
		Range curRange = new Range(start,end);
		
		List<Range> freeRanges = new ArrayList<Range>();
		
		MergedTimePointsIterator iterator =
			new MergedTimePointsIterator(schedules);
		
		while (iterator.hasNext()) {
			TimePoint tp = iterator.next();
			next = tp.time;
			if (beginCounter == 0 && next > curRange.B) {
				curRange.E = next-1;
				freeRanges.add(curRange);
			}
			beginCounter += (tp.begin)?1:-1;
			if (beginCounter == 0 && next < end){
				curRange = new Range(next+1,end);
			}
		}
		if (beginCounter == 0 && next < end) {
			freeRanges.add(curRange);
		}
		return freeRanges;
	}
	
	private static class TimePoint {
		private int time;
		private boolean begin;
		private TimePoint(int t, boolean b) {
			time = t;
			begin = b;
		}
	}
	
	private static class MergedTimePointsIterator
			implements Iterator<TimePoint>{
	
		private PriorityQueue<TimePointsIterator> rangeHeap =
			new PriorityQueue<TimePointsIterator>();
		
		private MergedTimePointsIterator( List<Range> ... schedules ) {
			for ( List<Range> s : schedules ) {
				TimePointsIterator tpi = new TimePointsIterator(s);
				if (tpi.hasNext()) rangeHeap.offer(tpi); 
			}
		}

		public boolean hasNext() {return !rangeHeap.isEmpty();}

		public TimePoint next() {
			if (!hasNext()) throw new NoSuchElementException();
			TimePointsIterator tpi = rangeHeap.poll();
			TimePoint ret = tpi.next();
			if (tpi.hasNext()) rangeHeap.offer(tpi);
			return ret;
		}

		public void remove() {throw new UnsupportedOperationException();}
	}
	
	private static class TimePointsIterator
			implements Comparable<TimePointsIterator>, Iterator<TimePoint>{
		
		private List<Range> rangeList;
		private int rangePointer = 0;
		private boolean begin = true;
		
		private TimePointsIterator( List<Range> list ) {
			rangeList = list;
		}
		
		private int peek () throws NoSuchElementException {
			if (!hasNext()) throw new NoSuchElementException();
			Range range = rangeList.get(rangePointer);
			return (begin) ? range.B : range.E;
		}

		public int compareTo(TimePointsIterator o) {
			return Integer.compare(peek(), o.peek());
		}

		public boolean hasNext() {
			return rangePointer < rangeList.size();
		}

		public TimePoint next() {
			TimePoint ret = new TimePoint(peek(),begin);
			if (!begin) rangePointer++;
			begin = !begin;
			return ret;
		}

		public void remove() {throw new UnsupportedOperationException();}
	}

From the two range lists, pick integers in order, regardless if they are beginning of range or the end, advancing either in one list or the other in order to keep ascending order of integers.

For every picked integer that is begining of range, increment begin counter, for every end decrement.

The free range is when begin counter is 0.

Obviously, linear time complexity.

static class Range {
	int B;
	int E;
	Range ( int b, int e) {
		B=b;
		E=e;
	}
	public String toString() { return "("+B+","+E+")";}
}	

public static List<Range> findFreeRanges
		(List<Range> per1, List<Range> per2, int start, int end) {
		
	int ind1=0;
	int ind2=0;
	int beginCounter = 0;
	int next = 0;
	Range curRange = new Range(start,end);
	List<Range> freeRanges =
		new ArrayList<Range>(per1.size() + per2.size());
		
	while (ind1 < per1.size()*2 || ind2 < per2.size()*2) {		
		int p1next = (ind1 < per1.size()*2)?
				((ind1%2==0)?per1.get(ind1/2).B:per1.get(ind1/2).E) :
				Integer.MAX_VALUE;
		int p2next = (ind2 < per2.size()*2)?
				((ind2%2==0)?per2.get(ind2/2).B:per2.get(ind2/2).E) :
				Integer.MAX_VALUE;	
		next = (p1next<p2next)?p1next:p2next;		
		if (beginCounter == 0 && next > curRange.B) {
			curRange.E = next-1;
			freeRanges.add(curRange);
		}
		if (p1next<p2next) {
			beginCounter += (ind1%2==0)?1:-1;
			ind1++;
		} else {
			beginCounter += (ind2%2==0)?1:-1;
			ind2++;
		}
		if (beginCounter == 0 && next < end){
			curRange = new Range(next+1,end);
		}
	}
	if (beginCounter == 0 && next < end) {
		freeRanges.add(curRange);
	}
	return freeRanges;
}
	
public static void  main ( String[] arg ) {
	System.out.println(findFreeRanges (
		new ArrayList(){{	add(new Range(1,5));
							add(new Range(10,14));
							add(new Range(19,20));
							add(new Range(21,24));
							add(new Range(27,30));}},
		new ArrayList(){{	add(new Range(3,5));
							add(new Range(12,15));
							add(new Range(18,21));
							add(new Range(23,24));}},
		1, 30));
}

- CT December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice idea!

- ninhnnsoc December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But, i wonder, how you pick numbers in right order. For example:
Person 1: (1, 20) (6, 15)
Person 2: (7, 9)
Please explain without code. Thanks!

- ninhnnsoc December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There way I understood the definition of the problem, for one person the ranges are non-overlaping. "increasing sequence of pair of numbers", does not say increasing begin point, but increasing pair. Also, reffers to calendar of one person, you cannot make it busy for two things at a time, I believe. It is almost obvious from problem statement, but @Phoenix, please confirm.

- CT December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

In addition, if they were overlaping, you would not have to make a problem with 2 persons.

- CT December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There will not be overlapping time as it is his meeting times, he cant be in two meetings at the same time

- Phoenix December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The code seems good, nice idea and complexity.

Otherwise the initial data is wrong. (22,22) should not be in the output since the first guy is busy in (21,24)

Thanks!

- Alb_Erc December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank, @Alb_Erc, my code did not output (22,22)

- CT December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//My turn: Scan through each of the intervals and search for the gaps in each of the intervals starting with 1. Time complexity is O(m+n)

	private static class Interval {
		public Interval(int start, int end) {
			this.start = start;
			this.end = end;
		}
		int start, end;
		@Override
		public String toString() {
			return String.format("(%d,%d)", start, end);
		}
	}

	// This method is useful to extract the interval from the list
	// if the index exceeds size, backupInterval
	public static Interval getInterval(List<Interval> list, int index,
			Interval backUpInterval) {
		if (list.size() - 1 < index)
			return backUpInterval;
		return list.get(index);
	}

	// Time complexity is O(m+n)
	public static List<Interval> findFreeIntervals(List<Interval> list1,
			List<Interval> list2) {
		int currentStart = 0;
		int currentEnd = 0;
		List<Interval> freeIntervals = new ArrayList<Interval>();
		Interval first = null;
		Interval second = null;
		// Loop through the max of the intervals
		for (int i = 0; i < Math.max(list1.size(), list2.size()); i++) {
			currentStart = currentEnd + 1;
			// get the next interval from each of the lists
			first = getInterval(list1, i, first);
			second = getInterval(list2, i, second);
			// get minimum and maximum of both intervals
			int minStart = Math.min(first.start, second.start);
			int maxEnd = Math.max(first.end, second.end);
			// End of the current busy interval
			currentEnd = maxEnd;

			// if there is a difference between one start interval start time
			// and another end time
			// then that is one free interval
			if (minStart > currentStart) {
				Interval freeInterval = new Interval(currentStart, minStart - 1);
				freeIntervals.add(freeInterval);
			}
			if (first.start > second.end) {
				Interval freeInterval = new Interval(second.end + 1,
						first.start - 1);
				freeIntervals.add(freeInterval);

			}
			if (second.start > first.end) {
				Interval freeInterval = new Interval(first.end + 1,
						first.start - 1);
				freeIntervals.add(freeInterval);

			}
			// If the size exceeds size, then take the previous of the other
			// intervals
			// for future consideration
			if (i == list1.size()) {
				first = second;
			}
			if (i == list2.size()) {
				second = first;
			}
		}
		return freeIntervals;

	}

	public static void main(String[] args) {
		// per1: (1,5) (10, 14) (19,20) (21,24) (27,30)
		// per2: (3,5) (12,15) (18, 21) (23, 24)
		Interval[] intervals = new Interval[] { new Interval(1, 5),
				new Interval(10, 14), new Interval(19, 20),
				new Interval(21, 24), new Interval(27, 30) };
		Interval[] intervals2 = new Interval[] { new Interval(3, 5),
				new Interval(12, 15), new Interval(18, 21),
				new Interval(23, 24) };
		System.out.println(findFreeIntervals(Arrays.asList(intervals), Arrays.asList(intervals2)));
	}

- naren December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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


public class Calendar {

	static class Meeting {
		int startTime;
		int endTime;

		public Meeting(int start, int end) {
			this.startTime = start;
			this.endTime = end;
		}

		public int getStartTime() {
			return startTime;
		}

		public void setStartTime(int startTime) {
			this.startTime = startTime;
		}

		public int getEndTime() {
			return endTime;
		}

		public void setEndTime(int endTime) {
			this.endTime = endTime;
		}

		public String toString() {
			return "( " + startTime + "," + endTime + " )";
		}
	}

	public static List<Meeting> freeTime(List<Meeting> list1, List<Meeting> list2) {
		List<Meeting> sortedMeetings = new ArrayList<>();

		int limit = list1.size();
		if (list1.size() <= list2.size()) {
			limit = list2.size();
		}

		for (int i = 0; i < limit; i++) {
			Meeting meeting1 = null;
			Meeting meeting2 = null;
			if (i < list1.size()) {
				meeting1 = list1.get(i);
			}

			if (i < list2.size()) {
				meeting2 = list2.get(i);
			}

			if (meeting1 != null && meeting2 != null) {
				if (meeting1.getStartTime() <= meeting2.getStartTime()) {
					sortedMeetings.add(meeting1);
					sortedMeetings.add(meeting2);
				} else {
					sortedMeetings.add(meeting2);
					sortedMeetings.add(meeting1);
				}

			} else if (meeting1 == null && meeting2 != null) {
				sortedMeetings.add(meeting2);

			} else if (meeting1 != null && meeting2 == null) {
				sortedMeetings.add(meeting1);
			}
		}

		List<Meeting> freeSlots = new ArrayList<Meeting>();

		for (int i = 0; i < sortedMeetings.size(); i++) {
			Meeting duration1 = null;
			Meeting duration2 = null;
			if (i < sortedMeetings.size() - 1) {
				duration1 = sortedMeetings.get(i);
				duration2 = sortedMeetings.get(i + 1);

				if (duration1.getEndTime() < duration2.getStartTime()) {
					freeSlots.add(new Meeting(duration1.getEndTime(), duration2.getStartTime()));
				}
			}
		}

		return freeSlots;
	}

	public static void printDurationList(List<Meeting> durationList) {
		System.out.println("================================");
		for (Meeting duration : durationList) {
			System.out.println(duration);
		}
	}

	public static void main(String[] args) {
		List<Meeting> list1 = new ArrayList<Meeting>();
		list1.add(new Meeting(1, 5));
		list1.add(new Meeting(10, 14));
		list1.add(new Meeting(19, 20));
		list1.add(new Meeting(21, 24));
		list1.add(new Meeting(27, 30));

		List<Meeting> list2 = new ArrayList<Meeting>();
		list2.add(new Meeting(3, 5));
		list2.add(new Meeting(12, 15));
		list2.add(new Meeting(18, 21));
		list2.add(new Meeting(23, 24));

		List<Meeting> freeTimes = freeTime(list1, list2);
		
		printDurationList(freeTimes);

	}

}

- Lasantha78 December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will fail with times (18, 21), (19, 20), (23,24) if the date 21,24 were not in the list.

19,20 comes after 18,21, and it will create an open date from 21-22, even though one person is busy on the 21st.

I like the idea of combining the two lists into one, but you should try to incorporate a way of storing a temporary start and end for each new free range so it doesn't forget about dates that don't meet your current criteria.

- Dan H December 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the meetings sets are passed in as int[][], then the problem can be solved in O(m+n) by simply merging both lists of events and scanning the merged list of occupied times. Merging works because we are searching for places in which nothing is scheduled. If even one of the individuals have something scheduled, then there isn't free time.

pseudo code:
list = merge both lists by sorting on the start of the occupied time (O (m + n) )
workingEnd = 1 (assuming that the calendar starts with 1)
for each event i = 0 .. n
if list[i] start <= working end
if list[i] end >= workingEnd
workingEnd = list[i] end + 1
else
add new event to results with start = workingEnd and end = event[i] start -1
workingEnd = event[i] end
return results

public static int[][] getFreeTimes(int[][] person1, int[][] person2){
	//merge
	int[][] list = merge(person1, person1);
	//do the rest
	ArrayList<int[]> results = new ArrayList<int[]>();
	int workingEnd = 1;
	for(int[] event : list){
		if(event[0] <= workingEnd){
			if(event[1] >= workingEnd){
				workingEnd = event[1]+1;
			}
		}
		else{
			results.add(new int[]{workingEnd, event[1]-1});
			workingEnd = event[1]+1;
		}
	}
	return results.toArray();
}

private static int[][] merge(int[][] arr1, int[][] arr2){
	int i = 0;
	int j = 0;
	int[][] results = new int[arr1.length + arr2.length][];
	int k = 0;
	while(i < arr1.length && j < arr2.length){
		if(arr1[i][0] <= arr2[j][0]){
			results[k] = arr1[i];
			i++;
		}
		else{
			results[k] = arr2[j];
			j++;
		}
		k++;
	}
	for(; i < arr1.length; i++){
		results[k] = arr1[i];
		k++;
	}
	for(; j < arr2.length; j++){
		results[k] = arr2[j];
		k++;
	}
	return results;
}

- zortlord December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

With this line
results.add(new int[]{workingEnd, event[1]-1});
we could possibly have gone past next event times. We should include additional check in here

- Srikanth December 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

results.add(new int[]{workingEnd, event[1]-1});
Should this be:results.add(new int[]{workingEnd, event[0]-1}); ?
lastWorkingEnd-startOfCurrentEvent-1

- jeffery June 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Should this line: results.add(new int[]{workingEnd, event[1]-1});
be results.add(new int[]{workingEnd, event[0]-1}); ???
freetime is lastWorkingEnd - startOfCurrentEvent-1?

- Jeffery.yuan June 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would create zero arrays for each person. Then use the ranges for each person to change each index corresponding to an available time to a 1. Then compare each person's array and matching 1's correspond to mutual intervals.

- Anonymous December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

$a = [[1, 5], [10, 14], [19, 20], [21, 24], [27, 30], [35, 39]];
$b = [[3, 5], [12, 15], [18, 21], [23, 24]];

$x = 0;
$times = [];
while ($x < max(count($a), count($b))) {

$aaMinTime = $a[$x][0] ?: INF;
$bbMinTime = $b[$x][0] ?: INF;
$start = min($aaMinTime, $bbMinTime);

if ($end && $start != $end) {
$times[] = [$end, $start];
}

$aaMaxTime = $a[$x][1];
$bbMaxTime = $b[$x][1];
$end = max($aaMaxTime, $bbMaxTime);

$x++;
}

var_dump($times);

- Wumpus December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

$a = [[1, 5], [10, 14], [19, 20], [21, 24], [27, 30], [35, 39]];
$b = [[3, 5], [12, 15], [18, 21], [23, 24]];

$x = 0;
$times = [];
while ($x < max(count($a), count($b))) {

	$aaMinTime = $a[$x][0] ?: INF;
	$bbMinTime = $b[$x][0] ?: INF;
	$start = min($aaMinTime, $bbMinTime);

	if ($end && $start != $end) {
		$times[] = [$end + 1, $start - 1];
	}

	$aaMaxTime = $a[$x][1];
	$bbMaxTime = $b[$x][1];
	$end = max($aaMaxTime, $bbMaxTime);

	$x++;
}

var_dump($times);

- voidet@nightgen.com December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

- Define boolean array busyHours with false values from startHour until endHour
- Iterate person1 and person2 times and set appropriate flags in the boolean array to true
- Go through resulted busyHours array and find flags with false value. It's free time

- SE Engineer December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public class MeetingTime {

	static List<Interval> findAvailableIntervalList(List<Interval> p1,
			List<Interval> p2) {

		List<Interval> mergedList = new ArrayList<>();

		Boolean[][] timeSlot = new Boolean[31][2];

		for (Interval mInterval : p1) {
			timeSlot[mInterval.open][0] = Boolean.TRUE;
			timeSlot[mInterval.close][0] = Boolean.FALSE;
		}

		for (Interval nInterval : p2) {
			timeSlot[nInterval.open][1] = Boolean.TRUE;
			timeSlot[nInterval.close][1] = Boolean.FALSE;
		}

		int openCounter = 0;
		int availableOpen = -1;

		for (int i = 0; i < 31; i++) {

			if (openCounter == 0) {
				if (null == timeSlot[i][0] && null == timeSlot[i][1]) {
					if (availableOpen == -1) {
						availableOpen = i;
					}
				} else {
					mergedList.add(new Interval(availableOpen, i - 1));
					availableOpen = -1;
				}
			}

			for (Boolean eachValue : timeSlot[i]) {
				if (Boolean.TRUE.equals(eachValue)) {
					openCounter++;
				} else if (Boolean.FALSE.equals(eachValue)) {
					openCounter--;
				}
			}
		}

		return mergedList;

	}

	public static void main(String[] args) {
		List<Interval> p1 = new ArrayList<>();
		List<Interval> p2 = new ArrayList<>();

		// per1: (1,5) (10, 14) (19,20) (21,24) (27,30)
		// per2: (3,5) (12,15) (18, 21) (23, 24)
		// ouput: (6,9) (16,17) (25,26)

		p1.add(new Interval(1, 5));
		p1.add(new Interval(10, 14));
		p1.add(new Interval(19, 20));
		p1.add(new Interval(21, 24));
		p1.add(new Interval(27, 30));

		p2.add(new Interval(3, 5));
		p2.add(new Interval(12, 15));
		p2.add(new Interval(18, 21));
		p2.add(new Interval(23, 24));

		for (Interval eachResult : findAvailableIntervalList(p1, p2)) {
			System.out
					.print(eachResult.open + " " + eachResult.close);
			System.out.println();
		}

	}

	static class Interval {
		int open;
		int close;

		Interval(int op, int cl) {
			this.open = op;
			this.close = cl;
		}
	}

}

- Barley December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The top solution here is great, but for me personally it would be a little bit difficult to make a clean code on a paper or a board for such approach during the interview. As we have O(N+M) memory complexity anyway for our output and don't have the constraint about not using additional data structures it is much easier, in my opinion, to merge two (or N) given arrays into one sorted by the starting points of intervals and then sweep it with simple iterative run.

public List<Interval> freeTimes(Interval[] per1, Interval[] per2) {
        if (per1 == null || per2 == null || per1.length == 0 || per2.length == 0) {
            return Collections.emptyList();
        }
        List<Interval> merged = new ArrayList<>();
        int i = 0, j = 0;
        while (i < per1.length && j < per2.length) {
            if (per1[i].a < per2[j].b) merged.add(per1[i++]);
            else merged.add(per2[j++]);
        }
        while (i < per1.length) merged.add(per1[i++]);
        while (j < per2.length) merged.add(per2[j++]);
        List<Interval> result = new ArrayList<>();
        for (int k = 0; k < merged.size()-1; k++) {
            Interval curr = merged.get(k);
            while (k < merged.size()-1 && merged.get(k).b < curr.b) k++;
            if (curr.b < merged.get(k+1).a-1)
                result.add(new Interval(curr.b+1, merged.get(k+1).a-1));
        }
        return result;
    }

- andreytim December 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

first of all your output has problem because 22 is inside the interval 21,24. A simple approach wuld be like this:

myl = []
set_list = [(1,5), (10, 14), (19,20), (21,24), (27,30) ]
for tuple_x in set_list:
    a,b = tuple_x
    for i in range(a,b+1):
        myl.append(i)

set_list = [(3,5), (12,15), (18, 21), (23, 24) ]
for tuple_x in set_list:
    a,b = tuple_x
    for i in range(a,b+1):
        myl.append(i)

myl.sort()
output = []
print myl
for i,j in enumerate(myl):
    if j == myl[-1]:
        break
    x = myl[i+1]

    if ((x-j) != 0) and ((x-j) != 1):
        output.append((j+1,x-1))
print output

- Anonymous December 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems to work for the test data set.

import java.util.*;

public class CalendarAvailability {
	   
	public static void main(String[] args){
		Interval[] p1 = {new Interval(21,24), new Interval(2,5), new Interval(19,20), new Interval(10, 14), new Interval(27,30)};
		Interval[] p2 = {new Interval(18, 21), new Interval(3,5), new Interval(23, 24), new Interval(12,15)};
		List<Interval> avail = findAvailability(p1, p2);
		
	}
	
	public static List<Interval> findAvailability(Interval[] person1, Interval[] person2){
		Arrays.sort(person1);
		Arrays.sort(person2);
		
		List<Interval> freeTimes = new ArrayList();
		Interval p1Interval = null, p2Interval = null;
		int index = 0, previousEnd = 1, start = 1, end = 1;

		while(index < Math.max(person1.length, person2.length)){
			p1Interval = getInterval(person1, index, person2);
			p2Interval = getInterval(person2, index, person1);
			
		    start = Math.min(p1Interval.startTime, p2Interval.startTime);
			end = Math.max(p1Interval.endTime, p2Interval.endTime);
			
			if(previousEnd < start)
				freeTimes.add(new Interval(previousEnd, start-1));
	
			previousEnd = end + 1;
			index++;
	    }
		
		return freeTimes;
	}
	
	public static Interval getInterval(Interval[] iList, int index, Interval[] backupList){
		Interval interval = null;
		
		if(index<iList.length)
			interval = iList[index];
		else
			interval = backupList[index];
		
		assert(interval!=null) : "interval is not allowed to be null";
		return interval;
 	}
	
    static class Interval implements Comparable{
		int startTime;
		int endTime;
		
		public Interval(int start, int end){
			this.startTime = start;
			this.endTime = end;
		}
		
		public int compareTo(Object o){
			Interval obj = (Interval)o;
			return compare(this.startTime, obj.endTime);
		}
		
		public static int compare(int x, int y) {
	        return (x < y) ? -1 : ((x == y) ? 0 : 1);
	    }
	}

}

- Er December 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Short O(n) solution (C++11)

#include <stdio.h>
#include <vector>
using namespace std;

typedef pair<int, int> App;

void FindFreeSlots(const vector<App>& v1, const vector<App>& v2)
{
  auto i1 = v1.begin();
  auto i2 = v2.begin();

  while (i1+1 != v1.end() || i2+1 != v2.end()) {
    int start = max(i1->second, i2->second) + 1;
    int end = 0;

    if (i1+1 == v1.end()) {
      end = (i2+1)->first - 1;
      ++i2;
    } else if (i2+1 == v2.end()) {
      end = (i1+1)->first - 1;
      ++i1;
    } else {
      end = min((i1+1)->first, (i2+1)->first) - 1;
      if ((i1+1)->first < (i2+1)->first)
        ++i1;
      else
        ++i2;
    }

    if (end-start > 0)
      printf("(%d, %d)\n", start, end);
  }
}

int main() {
  FindFreeSlots({{1,5}, {10, 14}, {19, 20}, {21,24}, {27, 30}},
                {{3, 5}, {12, 15}, {18, 21}, {23, 24}});
  // ouput: (6,9) (16,17) (25,26)
  return 0;
}

- Tobi December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Someone is downvoting last answers...I wonder why.

- Eugene Mmmmm December 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm
1)Put the time stamp as index and if free 0 and 1
2)Construct a bitset (bitmap) B1 ,B2
3)!(B1 || B2)-->free time f both

- bjovi December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about bitwise operations??
use a 32bit int to construct the busy schedule per person and with an ior (|) opearation, the 0 bits will have the free time slots for both...

- burton123 December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Class FreeTimeFinder{

public static List<Interval> findFreeTimes(Interval[] per1, Interval[] per2){
if((per1==null)||(per2==null)||(per1.length==0)|| (per2.length==0)){
return null;
}
List<Interval> freeTimesPer1=findFreeTimes(per1);
Interval[] freeTimesPer2=findFreeTimes(per2).toArray();

List<Interval> mutualTimes=new ArrayList<Interval>();//contains mutually available times for person 1 and person 2
Iterator<Interval> it= freeTimesPer1.iterator();
while(it.hasNext()){
Interval p1Interval=it.next();
int overlapIdx=Arrays.binarySearch(p1Interval,freeTimesPer2);
if(overlapIdx!=-1){
Interval p2Interval=freeTimesPer2[overlapIdx];
if(p1Interval.end-p1.Interval.start <= p2Interval.end-p2Interval.start){
mutualTimes.add(p1Interval);
}else{
mutualTimes.add(p2Interval);
}
}

}
return mutualTimes;
}

private List<Interval> findFreeTimes(Interval[] busyTimes){
List<Interval> freeTimes=new ArrayList<Interval>();
for(int i=1; i<busyTimes.length;i++){
Interval first=busyTimes[i-1];
Interval sec=busyTimes[i];
if(first.end - sec.start => 1){
freeTimes.add(new Interval(first.end+1,sec.start-1));
}
}
return freeTimes;
}

class IntervalComparator implements Comparable{
public int compare(Interval i1,Interval i2){
if(i1.end<=i2.start){
return -1;//Indicates that interval i1 occurrs before interval i2
}else if(i1.start>=i2.end){
return 1;//Indicates that interval i1 occurrs after interval i2
}
return 0;//Indicates that interval i1 overlaps with interval i2
}
}

public static void main(String[] args){
Interval[] per1={new Interval(2,3),new Interval(4,7),new Interval(27,30)};
Interval[] per2={new Interval(1,2),new Interval(6,7),new Interval(22,25), new Interval(27,29)};

FreeTimeFinder() ft=new FreeTimeFinder();
List<Interval> mutualTimes=ft.findFreeTimes(per1,per2);
}

}

- divm01986 December 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code:
In the above e.g. there is a value(22,22). not sure if that really makes sense, and avoided it in my code. its a small change to include it back in.

def freetime(per1, per2):
    c_freetime=computefreetime(per1, per2)
    for i in range(len(c_freetime)-1):
        if c_freetime[i+1][0]-c_freetime[i][1]>2:
            print (c_freetime[i][1]+1, c_freetime[i+1][0]-1),


def computefreetime(per1, per2):
    temp=[]
    i=0
    j=0
    while i<len(per1):
        while j<len(per2):
            if max(per1[i])<min(per2[j]):
                temp.append(per1[i])
                i+=1
            elif max(per2[j])<min(per1[i]):
                temp.append(per2[j])
                j+=1
            else:
                x=(min(per1[i][0],per2[j][0]),max(per1[i][1],per2[j][1]))
                temp.append(x)
                i+=1
                j+=1
        if i==len(per1) or j==len(per2):
            break
    while i<len(per1):
        temp.append(per1[i])
        i+=1
    while j<len(per2):
        temp.append(per2[j])
        j+=1
    return temp

- Murali December 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the list of intervals and just iterate through them - Simple O(n+m) solution as others have shown

class Interval {
public:    
    int _start;
    int _end;
    int getLength() { return (_end - _start); };
    
    Interval(int i, int j) : _start(i), _end(j)  {};
    
    bool operator<(Interval &i1);  
    
    bool operator() (Interval &i1, Interval &i2);
};

bool Interval::operator< (Interval &i1) {
    return (i1._start < _start);
}

bool Interval::operator() (Interval &i1, Interval &i2) {
    return (i1._start < i2._start);
}

bool classComp(Interval *i1, Interval *i2) {return (i1->_start < i2->_start);}

void findFreeCalendarTimes() {

    vector<Interval *> I1, I2;
    vector<Interval *>::iterator it;

    I1.push_back(new Interval(1,5));
    I1.push_back(new Interval(10,14));    
    I1.push_back(new Interval(19,20));
    I1.push_back(new Interval(21,24));
    I1.push_back(new Interval(27,30));
    I1.push_back(new Interval(3,5));
    I1.push_back(new Interval(12,15));
    I1.push_back(new Interval(18,21));
    I1.push_back(new Interval(23,24));
    
    sort(I1.begin(), I1.end(), classComp);

    for(it=I1.begin(); it!=I1.end(); it++) cout << " " << (*it)->_start << " " << (*it)->_end << endl;
    
    it = I1.begin();
    int prev_end = (*it)->_end;
    for(it=I1.begin(); it!=I1.end(); it++) {
        if(prev_end<(*it)->_start) {
            cout << "Found " << prev_end+1 << " "  << (*it)->_start-1 << endl;
            prev_end = (*it)->_end;
        }else {
            if(prev_end < (*it)->_end)
                prev_end = (*it)->_end;
        }
    }    
}

- D December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Short and precise O(n) solution

#include<iostream>
using namespace std;

struct limit
{
    int lowerl;
    int upperl;
};

void func_populate(int arr[],limit person[],int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=person[i].lowerl;j<=person[i].upperl;j++)
        {
            arr[j]=1;
        }
    }
}

int main()
{
    limit person1[] = { {1,5}, {10, 14}, {19,20}, {21,24}, {27,30} };
    limit person2[]={ {3,5} ,{12,15}, {18, 21}, {23, 24}  };

    int n1=sizeof(person1)/sizeof(person1[0]);
    int n2=sizeof(person2)/sizeof(person2[0]);

    int max1,max2;
    max1=person1[n1-1].upperl;
    max2=person2[n2-1].upperl;
    int fin_max;

    if(max1>max2)
    {
        fin_max=max1;
    }
    else
    {
        fin_max=max2;
    }

    int a[fin_max+5];
    int b[fin_max+5];
    int c[fin_max+5];
    fill(a,a+fin_max+1,0);
    fill(b,b+fin_max+1,0);

    func_populate(a,person1,n1);
    func_populate(b,person2,n2);


    for(int i=1;i<=fin_max;i++)
    {
        c[i]=a[i] | b[i];
    }
    limit meeting[100];
    int c1=0;
    for(int i=1;i<=fin_max;i++)
    {
        if(c[i]==0)
        {
            meeting[c1].lowerl=i;
            while(c[i]==0)
                i++;
            meeting[c1].upperl=i-1;
            c1++;
        }
    }
    for(int i=0;i<c1;i++)
    {
        cout<<"\n("<<meeting[i].lowerl<<" , "<<meeting[i].upperl<<")";
    }
    return 0;
}

- Charu Mehndiratta December 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can wrap the provided lists of busy-time ranges in a collection built to iterate over the free space (i.e. spaces between the elements). The free space collection would implement iterable and would correctly find ranges at the start, middle, and end of the time ranges for each list.

The time ranges can be held in a class which allows comparison to figure out which range ends sooner. The class could also take in two time ranges (which are also used for representing free time) and return the overlapping range.

Once we have all this, we can iterate over the free time collections, always advancing the "earlier ending" time range, looking for overlaps. Once we've stepped through both ranges, we've found all overlaps/available times.

package com.company;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class FreeTimeCollection implements Iterable<TimeSlot> {

    public static void main(String[] args) {
        List<TimeSlot> p1 = new ArrayList<>();
        List<TimeSlot> p2 = new ArrayList<>();

        p1.add(new TimeSlot(1, 5));   //6-9
        p1.add(new TimeSlot(10, 14)); //15-18
        p1.add(new TimeSlot(19, 20));
        p1.add(new TimeSlot(21, 24)); //25-26
        p1.add(new TimeSlot(27, 30));

        p2.add(new TimeSlot(3, 5));   //1-2
        p2.add(new TimeSlot(12, 15)); //6-11
        p2.add(new TimeSlot(18, 21)); //16-17
        p2.add(new TimeSlot(23, 24)); //22-22
        //25-30

        FreeTimeCollection c1 = new FreeTimeCollection(p1);
        FreeTimeCollection c2 = new FreeTimeCollection(p2);

        //Find matching time slots between the two collections.  Should result in:
        // (6, 9) (16, 17) (25, 26).
        List<TimeSlot> times = c1.findMatchingTimeSlots(c2);
        for (TimeSlot t : times) {
            System.out.print(t + " ");
        }
    }

    private final static int MAX = 30;
    private List<TimeSlot> taken;

    public FreeTimeCollection(List<TimeSlot> takenSlots) {
        this.taken = takenSlots;
    }

    public List<TimeSlot> findMatchingTimeSlots(FreeTimeCollection other) {

        //Set up and validate the iterators.  Also retrieve the initial time slots.
        List<TimeSlot> freeTime = new ArrayList<>();
        Iterator<TimeSlot> c1i = iterator();
        Iterator<TimeSlot> c2i = other.iterator();

        if (!c1i.hasNext() || !c2i.hasNext()) return freeTime;
        TimeSlot t1 = c1i.next();
        TimeSlot t2 = c2i.next();

        //If both are left, continually choose the lesser one.
        while (true) {
            TimeSlot ts = t1.findOverlap(t2);
            if (ts != null) {
                freeTime.add(ts);
            }
            if (!c1i.hasNext() || !c2i.hasNext()) break;
            int r = t1.compareTo(t2);
            if (r == -1) { t1 = c1i.next(); }
            else if (r == 1) { t2 = c2i.next(); }
            else {
                t1 = c1i.next();
                t2 = c2i.next();
            }
        }

        //Else drain the remaining one.
        while (c1i.hasNext() || c2i.hasNext()) {
            if (c1i.hasNext()) t1 = c1i.next();
            else if (c2i.hasNext()) t2 = c2i.next();
            TimeSlot ts = t1.findOverlap(t2);
            if (ts != null) {
                freeTime.add(ts);
            }
        }

        //Return the free time array.
        return freeTime;
    }

    //Provide an iterator to move over the free time slots.
    @Override
    public Iterator<TimeSlot> iterator() {
        return new Iterator<TimeSlot>() {

            int curr = 0;
            int next = 1;
            boolean isFirst = true;
            boolean done = false;
            TimeSlot nextFreeSlot = getNext();

            @Override
            public boolean hasNext() {
                return nextFreeSlot != null;
            }

            @Override
            public TimeSlot next() {
                TimeSlot slot = nextFreeSlot;
                nextFreeSlot = getNext();
                return slot;
            }

            //Automatically assumed in constructor.
            private boolean isFirst() {
                return isFirst;
            }

            //We're in the mid if it's not the first and the current is not
            //yet on the last element since that means the next can be on the
            //last element.  True last is last --> null.
            private boolean isMid() {
                return !isFirst() && curr < taken.size() - 1;
            }

            //It is the last if the current is the last element.
            private boolean isLast() {
                return curr == taken.size() - 1;
            }

            private TimeSlot getNext() {

                while (!isLast()) {

                    TimeSlot tsc = taken.get(curr);
                    TimeSlot tsn = next > taken.size() - 1 ? null : taken.get(next);

                    if (isFirst()) {
                        isFirst = false;
                        if (tsc.start == 1) continue;
                        else {
                            return new TimeSlot(1, tsc.start - 1);
                        }
                    }

                    if (isMid()) {
                        curr = next;
                        next = next +1;
                        if (tsn.start - tsc.end > 1) {
                            return new TimeSlot(tsc.end + 1, tsn.start - 1);
                        }
                        else continue;
                    }
                }

                TimeSlot end = taken.get(taken.size() - 1);
                if (end.end < MAX && !done) {
                    done = true;
                    return new TimeSlot(end.end + 1, MAX);
                }

                return null;
            }
        };
    }
}

package com.company;

public class TimeSlot implements Comparable<TimeSlot> {

    public int start;
    public int end;

    public TimeSlot(int start, int end) {
        this.start = start;
        this.end = end;
    }

    //Time slots are for free hours, start-end inclusive.  So, if there is any overlap
    //between the later start time and the earlier end time, we have a valid overlap.
    public TimeSlot findOverlap(TimeSlot other) {
        int maxStart = Math.max(start, other.start);
        int minEnd = Math.min(end, other.end);
        if (minEnd - maxStart >= 0) return new TimeSlot(maxStart, minEnd);
        return null;
    }

    //We care about which time slot ends first when we compare slots.  This lets us
    //take a "earlier" slot and advance it so that it may overlap with a "later" slot.
    @Override
    public int compareTo(TimeSlot other) {
        return Integer.compare(this.end, other.end);
    }

    @Override
    public String toString() {
        return "(" + start + ", " + end + ")";
    }
}

- w00te December 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You may also can do by recursive algorithm.

typedef vector< pair<int, int> > interval_vector;

void find_intervals(const interval_vector & A, const interval_vector & B,
					interval_vector & R, int idx_A, int idx_B){ 
	if (idx_A + 1 >= A.size()) return;
	if (idx_B + 1 >= B.size()) return;
	pair<int, int> a(A[idx_A].second, A[idx_A+1].first);
	pair<int, int> b(B[idx_B].second, B[idx_B+1].first);
	pair<int, int> r(max(a.first, b.first)+1, min(a.second, b.second)-1);
	if (r.second >= r.first) R.push_back(r);
	if (a.first < b.first) ++idx_A;
	else ++idx_B;
	return find_intervals(A, B, R, idx_A, idx_B);
}

void find_intervals(const interval_vector & A, const interval_vector & B,
					interval_vector & R) {
	interval_vector CA, CB;
	CA.push_back(make_pair(0,0));
	CB.push_back(make_pair(0,0));
	for (auto a : A) CA.push_back(a);
	for (auto b : B) CB.push_back(b);
	if (CA.back().second > CB.back().second) CB.push_back(make_pair(CA.back().second, CA.back().second));
	if (CA.back().second < CB.back().second) CA.push_back(make_pair(CB.back().second, CB.back().second));

	find_intervals(CA, CB, R, 0, 0);
}

- Someone January 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<TimePeriod> per1 = new  ArrayList<Main.TimePeriod>();
		per1.add(new TimePeriod(1,5));
		per1.add(new TimePeriod(10, 14));
		per1.add(new TimePeriod(19,20));
		per1.add(new TimePeriod(21,24));
		per1.add(new TimePeriod(27,27));
		per1.add(new TimePeriod(29,30));
		
		ArrayList<TimePeriod> per2 = new  ArrayList<Main.TimePeriod>();
		per2.add(new TimePeriod(3,5));
		per2.add(new TimePeriod(12,15));
		per2.add(new TimePeriod(18, 21));
		per2.add(new TimePeriod(23, 24));
		per2.add(new TimePeriod(29, 30));
		
		
		PersoneCalengerManger manager1 = new PersoneCalengerManger(per1);
		PersoneCalengerManger manager2 = new PersoneCalengerManger(per2);
		
		ArrayList<TimePeriod> free = PersoneCalengerManger.mergeFreeDays(manager1.getFreeDays(), manager2.getFreeDays());
		
		
		for(TimePeriod l:free)
			System.out.println(l.start+","+l.end);
		   

	}
	
	
	public static class TimePeriod
	{
		public int start;
		public int end;

		public TimePeriod(int a, int b)
		{
			start = a;
			end = b;
		}

		public void setStart(int a){start = a;}
		public void setEnd(int e){end = e;}
			
		public boolean caontains(int d)
		{
			return ((start<=d)&&(d<=end));
		}
	}

	public static class PersoneCalengerManger
	{
		public ArrayList<TimePeriod> busy;

		public PersoneCalengerManger(ArrayList<TimePeriod> per1)
		{
			this.busy = per1;
		}

		public ArrayList<Integer> getFreeDays()
		{
			ArrayList<Integer> days = new ArrayList<Integer>();
			for(int i=1;i<=30;i++)
				if(isFree(i))
					days.add(i);
			return days;
		}

		private boolean isFree(int d)
		{
			for(TimePeriod pr : busy)
				if(pr.caontains(d))
					return false;
			return true;
		}

		
		public  static  ArrayList<TimePeriod> mergeFreeDays (ArrayList<Integer> days1,ArrayList<Integer> days2)
		{
			ArrayList<TimePeriod> meeting = new ArrayList<TimePeriod>();
			ArrayList<Integer> freeDays = new ArrayList<Integer>();

			for(int i=0; i< days1.size(); i++)
			{
				if (days2.contains(days1.get(i)))
					freeDays.add(days1.get(i));
			}
		
			
			if(freeDays.size()>0)
			{
				int startD = freeDays.get(0);
				int endD;
				for(int i = 1 ; i<freeDays.size();i++)
				{
					if(freeDays.get(i)==freeDays.get(i-1)+1){}
					else
					{	endD = freeDays.get(i-1);
						meeting.add(new TimePeriod(startD,endD));
						startD = freeDays.get(i);
					}
						
				}
				meeting.add(new TimePeriod(startD, freeDays.get(freeDays.size()-1)));
			}
		
			return meeting;
		}

		

	}


}

- Slaheddine January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (23,24) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

Algo:
Find all free time points for each person
Find those common free time points of the two persons
Give the common free time slots

*/
void findCommonTimeSlots(int* per1, int size1, int* per2, int size2){
//Find all free time points for each person
const int maxTime=30;

int* free1 = new int[maxTime];
int freeSize1=0;
int* free2 = new int[maxTime];
int freeSize2=0;

//initialisation
int moment=1;
int index1=0;
while ((moment<=maxTime)&&(index1<size1)) {
if (moment==per1[index1]) //busy momment, move to check next time moment
{
moment++;
index1++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free1[freeSize1++] = moment;
//move to check next time moment
moment++;
}
}

int upper1 = per1[size1-1];
if (upper1<maxTime) //add all remaining free slots to the record
//if (per1[size1-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per1[size1-1]+1; i<=maxTime; i++)
{
free1[freeSize1++] = i;
}
}

cout << "free moments for person1 is :\n";
for (int i=0; i<freeSize1; i++)
cout << free1[i] << " ";
cout << "\n";

//initialisation
moment=1;
int index2=0;
while ((moment<=maxTime)&&(index2<size2)) {
if (moment==per2[index2]) //busy momment, move to check next time moment
{
moment++;
index2++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free2[freeSize2++] = moment;
//move to check next time moment
moment++;
}
}

if (per2[size2-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per2[size2-1]+1; i<=maxTime; i++)
{
free2[freeSize2++] = i;
}
}

cout << "free moments for person2 is :\n";
for (int i=0; i<freeSize2; i++)
cout << free2[i] << " ";
cout << "\n";


//Find those common free time points of the two persons
//reset start index for both free time record arrays
index1=0;
index2=0;
int maxfreeSize = (freeSize1>freeSize2)?freeSize1:freeSize2;
int* commonFree = new int[maxfreeSize];
int freeSize=0;

while ((index1<freeSize1)&&(index2<freeSize2))
{
if (free1[index1]==free2[index2]) //a common free moment is found
{
commonFree[freeSize++]=free1[index1];
//move to check next sample
index1++; index2++;
}
else if (free1[index1]< free2[index2])
index1++;
else //free1[index1] > free2[index2]
index2++;
}

cout << "common free moments for both persons are :\n";
for (int i=0; i<freeSize; i++)
cout << commonFree[i] << " ";
cout << "\n";


//Give the common free time slots
int startInd=0;
int endInd=startInd;
//find each common free time slot in sequence
cout << "All common free time slots are: \n";
while ((startInd<freeSize)&&(endInd<freeSize))
{
if (commonFree[endInd+1] == commonFree[endInd]+1) //continuous free slot, skip
{endInd++;}
else //a time slot is found
{
cout<< "(" << commonFree[startInd]<< "," <<commonFree[endInd]<<")\n";
startInd=endInd+1; //move to find next slot
endInd=startInd;
}
}

}

- Kevin February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (23,24) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

Algo:
Find all free time points for each person
Find those common free time points of the two persons
Give the common free time slots

*/
void findCommonTimeSlots(int* per1, int size1, int* per2, int size2){
//Find all free time points for each person
const int maxTime=30;

int* free1 = new int[maxTime];
int freeSize1=0;
int* free2 = new int[maxTime];
int freeSize2=0;

//initialisation
int moment=1;
int index1=0;
while ((moment<=maxTime)&&(index1<size1)) {
if (moment==per1[index1]) //busy momment, move to check next time moment
{
moment++;
index1++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free1[freeSize1++] = moment;
//move to check next time moment
moment++;
}
}

int upper1 = per1[size1-1];
if (upper1<maxTime) //add all remaining free slots to the record
//if (per1[size1-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per1[size1-1]+1; i<=maxTime; i++)
{
free1[freeSize1++] = i;
}
}

cout << "free moments for person1 is :\n";
for (int i=0; i<freeSize1; i++)
cout << free1[i] << " ";
cout << "\n";

//initialisation
moment=1;
int index2=0;
while ((moment<=maxTime)&&(index2<size2)) {
if (moment==per2[index2]) //busy momment, move to check next time moment
{
moment++;
index2++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free2[freeSize2++] = moment;
//move to check next time moment
moment++;
}
}

if (per2[size2-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per2[size2-1]+1; i<=maxTime; i++)
{
free2[freeSize2++] = i;
}
}

cout << "free moments for person2 is :\n";
for (int i=0; i<freeSize2; i++)
cout << free2[i] << " ";
cout << "\n";


//Find those common free time points of the two persons
//reset start index for both free time record arrays
index1=0;
index2=0;
int maxfreeSize = (freeSize1>freeSize2)?freeSize1:freeSize2;
int* commonFree = new int[maxfreeSize];
int freeSize=0;

while ((index1<freeSize1)&&(index2<freeSize2))
{
if (free1[index1]==free2[index2]) //a common free moment is found
{
commonFree[freeSize++]=free1[index1];
//move to check next sample
index1++; index2++;
}
else if (free1[index1]< free2[index2])
index1++;
else //free1[index1] > free2[index2]
index2++;
}

cout << "common free moments for both persons are :\n";
for (int i=0; i<freeSize; i++)
cout << commonFree[i] << " ";
cout << "\n";


//Give the common free time slots
int startInd=0;
int endInd=startInd;
//find each common free time slot in sequence
cout << "All common free time slots are: \n";
while ((startInd<freeSize)&&(endInd<freeSize))
{
if (commonFree[endInd+1] == commonFree[endInd]+1) //continuous free slot, skip
{endInd++;}
else //a time slot is found
{
cout<< "(" << commonFree[startInd]<< "," <<commonFree[endInd]<<")\n";
startInd=endInd+1; //move to find next slot
endInd=startInd;
}
}

}

- Kevin February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (23,24) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

Algo:
Find all free time points for each person
Find those common free time points of the two persons
Give the common free time slots

*/
void findCommonTimeSlots(int* per1, int size1, int* per2, int size2){
//Find all free time points for each person
const int maxTime=30;

int* free1 = new int[maxTime];
int freeSize1=0;
int* free2 = new int[maxTime];
int freeSize2=0;

//initialisation
int moment=1;
int index1=0;
while ((moment<=maxTime)&&(index1<size1)) {
if (moment==per1[index1]) //busy momment, move to check next time moment
{
moment++;
index1++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free1[freeSize1++] = moment;
//move to check next time moment
moment++;
}
}

int upper1 = per1[size1-1];
if (upper1<maxTime) //add all remaining free slots to the record
//if (per1[size1-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per1[size1-1]+1; i<=maxTime; i++)
{
free1[freeSize1++] = i;
}
}

cout << "free moments for person1 is :\n";
for (int i=0; i<freeSize1; i++)
cout << free1[i] << " ";
cout << "\n";

//initialisation
moment=1;
int index2=0;
while ((moment<=maxTime)&&(index2<size2)) {
if (moment==per2[index2]) //busy momment, move to check next time moment
{
moment++;
index2++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free2[freeSize2++] = moment;
//move to check next time moment
moment++;
}
}

if (per2[size2-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per2[size2-1]+1; i<=maxTime; i++)
{
free2[freeSize2++] = i;
}
}

cout << "free moments for person2 is :\n";
for (int i=0; i<freeSize2; i++)
cout << free2[i] << " ";
cout << "\n";


//Find those common free time points of the two persons
//reset start index for both free time record arrays
index1=0;
index2=0;
int maxfreeSize = (freeSize1>freeSize2)?freeSize1:freeSize2;
int* commonFree = new int[maxfreeSize];
int freeSize=0;

while ((index1<freeSize1)&&(index2<freeSize2))
{
if (free1[index1]==free2[index2]) //a common free moment is found
{
commonFree[freeSize++]=free1[index1];
//move to check next sample
index1++; index2++;
}
else if (free1[index1]< free2[index2])
index1++;
else //free1[index1] > free2[index2]
index2++;
}

cout << "common free moments for both persons are :\n";
for (int i=0; i<freeSize; i++)
cout << commonFree[i] << " ";
cout << "\n";


//Give the common free time slots
int startInd=0;
int endInd=startInd;
//find each common free time slot in sequence
cout << "All common free time slots are: \n";
while ((startInd<freeSize)&&(endInd<freeSize))
{
if (commonFree[endInd+1] == commonFree[endInd]+1) //continuous free slot, skip
{endInd++;}
else //a time slot is found
{
cout<< "(" << commonFree[startInd]<< "," <<commonFree[endInd]<<")\n";
startInd=endInd+1; //move to find next slot
endInd=startInd;
}
}

}

- Kevin February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (23,24) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

Algo:
Find all free time points for each person
Find those common free time points of the two persons
Give the common free time slots

*/
void findCommonTimeSlots(int* per1, int size1, int* per2, int size2){
//Find all free time points for each person
const int maxTime=30;

int* free1 = new int[maxTime];
int freeSize1=0;
int* free2 = new int[maxTime];
int freeSize2=0;

//initialisation
int moment=1;
int index1=0;
while ((moment<=maxTime)&&(index1<size1)) {
if (moment==per1[index1]) //busy momment, move to check next time moment
{
moment++;
index1++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free1[freeSize1++] = moment;
//move to check next time moment
moment++;
}
}

int upper1 = per1[size1-1];
if (upper1<maxTime) //add all remaining free slots to the record
//if (per1[size1-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per1[size1-1]+1; i<=maxTime; i++)
{
free1[freeSize1++] = i;
}
}

cout << "free moments for person1 is :\n";
for (int i=0; i<freeSize1; i++)
cout << free1[i] << " ";
cout << "\n";

//initialisation
moment=1;
int index2=0;
while ((moment<=maxTime)&&(index2<size2)) {
if (moment==per2[index2]) //busy momment, move to check next time moment
{
moment++;
index2++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free2[freeSize2++] = moment;
//move to check next time moment
moment++;
}
}

if (per2[size2-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per2[size2-1]+1; i<=maxTime; i++)
{
free2[freeSize2++] = i;
}
}

cout << "free moments for person2 is :\n";
for (int i=0; i<freeSize2; i++)
cout << free2[i] << " ";
cout << "\n";


//Find those common free time points of the two persons
//reset start index for both free time record arrays
index1=0;
index2=0;
int maxfreeSize = (freeSize1>freeSize2)?freeSize1:freeSize2;
int* commonFree = new int[maxfreeSize];
int freeSize=0;

while ((index1<freeSize1)&&(index2<freeSize2))
{
if (free1[index1]==free2[index2]) //a common free moment is found
{
commonFree[freeSize++]=free1[index1];
//move to check next sample
index1++; index2++;
}
else if (free1[index1]< free2[index2])
index1++;
else //free1[index1] > free2[index2]
index2++;
}

cout << "common free moments for both persons are :\n";
for (int i=0; i<freeSize; i++)
cout << commonFree[i] << " ";
cout << "\n";


//Give the common free time slots
int startInd=0;
int endInd=startInd;
//find each common free time slot in sequence
cout << "All common free time slots are: \n";
while ((startInd<freeSize)&&(endInd<freeSize))
{
if (commonFree[endInd+1] == commonFree[endInd]+1) //continuous free slot, skip
{endInd++;}
else //a time slot is found
{
cout<< "(" << commonFree[startInd]<< "," <<commonFree[endInd]<<")\n";
startInd=endInd+1; //move to find next slot
endInd=startInd;
}
}

}

- Kevin February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (23,24) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

Algo:
Find all free time points for each person
Find those common free time points of the two persons
Give the common free time slots

*/
void findCommonTimeSlots(int* per1, int size1, int* per2, int size2){
//Find all free time points for each person
const int maxTime=30;

int* free1 = new int[maxTime];
int freeSize1=0;
int* free2 = new int[maxTime];
int freeSize2=0;

//initialisation
int moment=1;
int index1=0;
while ((moment<=maxTime)&&(index1<size1)) {
if (moment==per1[index1]) //busy momment, move to check next time moment
{
moment++;
index1++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free1[freeSize1++] = moment;
//move to check next time moment
moment++;
}
}

int upper1 = per1[size1-1];
if (upper1<maxTime) //add all remaining free slots to the record
//if (per1[size1-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per1[size1-1]+1; i<=maxTime; i++)
{
free1[freeSize1++] = i;
}
}

cout << "free moments for person1 is :\n";
for (int i=0; i<freeSize1; i++)
cout << free1[i] << " ";
cout << "\n";

//initialisation
moment=1;
int index2=0;
while ((moment<=maxTime)&&(index2<size2)) {
if (moment==per2[index2]) //busy momment, move to check next time moment
{
moment++;
index2++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free2[freeSize2++] = moment;
//move to check next time moment
moment++;
}
}

if (per2[size2-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per2[size2-1]+1; i<=maxTime; i++)
{
free2[freeSize2++] = i;
}
}

cout << "free moments for person2 is :\n";
for (int i=0; i<freeSize2; i++)
cout << free2[i] << " ";
cout << "\n";


//Find those common free time points of the two persons
//reset start index for both free time record arrays
index1=0;
index2=0;
int maxfreeSize = (freeSize1>freeSize2)?freeSize1:freeSize2;
int* commonFree = new int[maxfreeSize];
int freeSize=0;

while ((index1<freeSize1)&&(index2<freeSize2))
{
if (free1[index1]==free2[index2]) //a common free moment is found
{
commonFree[freeSize++]=free1[index1];
//move to check next sample
index1++; index2++;
}
else if (free1[index1]< free2[index2])
index1++;
else //free1[index1] > free2[index2]
index2++;
}

cout << "common free moments for both persons are :\n";
for (int i=0; i<freeSize; i++)
cout << commonFree[i] << " ";
cout << "\n";


//Give the common free time slots
int startInd=0;
int endInd=startInd;
//find each common free time slot in sequence
cout << "All common free time slots are: \n";
while ((startInd<freeSize)&&(endInd<freeSize))
{
if (commonFree[endInd+1] == commonFree[endInd]+1) //continuous free slot, skip
{endInd++;}
else //a time slot is found
{
cout<< "(" << commonFree[startInd]<< "," <<commonFree[endInd]<<")\n";
startInd=endInd+1; //move to find next slot
endInd=startInd;
}
}

}

- Kevin February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (23,24) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

Algo:
Find all free time points for each person
Find those common free time points of the two persons
Give the common free time slots

*/
void findCommonTimeSlots(int* per1, int size1, int* per2, int size2){
//Find all free time points for each person
const int maxTime=30;

int* free1 = new int[maxTime];
int freeSize1=0;
int* free2 = new int[maxTime];
int freeSize2=0;

//initialisation
int moment=1;
int index1=0;
while ((moment<=maxTime)&&(index1<size1)) {
if (moment==per1[index1]) //busy momment, move to check next time moment
{
moment++;
index1++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free1[freeSize1++] = moment;
//move to check next time moment
moment++;
}
}

int upper1 = per1[size1-1];
if (upper1<maxTime) //add all remaining free slots to the record
//if (per1[size1-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per1[size1-1]+1; i<=maxTime; i++)
{
free1[freeSize1++] = i;
}
}

cout << "free moments for person1 is :\n";
for (int i=0; i<freeSize1; i++)
cout << free1[i] << " ";
cout << "\n";

//initialisation
moment=1;
int index2=0;
while ((moment<=maxTime)&&(index2<size2)) {
if (moment==per2[index2]) //busy momment, move to check next time moment
{
moment++;
index2++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free2[freeSize2++] = moment;
//move to check next time moment
moment++;
}
}

if (per2[size2-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per2[size2-1]+1; i<=maxTime; i++)
{
free2[freeSize2++] = i;
}
}

cout << "free moments for person2 is :\n";
for (int i=0; i<freeSize2; i++)
cout << free2[i] << " ";
cout << "\n";


//Find those common free time points of the two persons
//reset start index for both free time record arrays
index1=0;
index2=0;
int maxfreeSize = (freeSize1>freeSize2)?freeSize1:freeSize2;
int* commonFree = new int[maxfreeSize];
int freeSize=0;

while ((index1<freeSize1)&&(index2<freeSize2))
{
if (free1[index1]==free2[index2]) //a common free moment is found
{
commonFree[freeSize++]=free1[index1];
//move to check next sample
index1++; index2++;
}
else if (free1[index1]< free2[index2])
index1++;
else //free1[index1] > free2[index2]
index2++;
}

cout << "common free moments for both persons are :\n";
for (int i=0; i<freeSize; i++)
cout << commonFree[i] << " ";
cout << "\n";


//Give the common free time slots
int startInd=0;
int endInd=startInd;
//find each common free time slot in sequence
cout << "All common free time slots are: \n";
while ((startInd<freeSize)&&(endInd<freeSize))
{
if (commonFree[endInd+1] == commonFree[endInd]+1) //continuous free slot, skip
{endInd++;}
else //a time slot is found
{
cout<< "(" << commonFree[startInd]<< "," <<commonFree[endInd]<<")\n";
startInd=endInd+1; //move to find next slot
endInd=startInd;
}
}

}

- Kevin February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
/*
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (23,24) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

Algo:
Find all free time points for each person
Find those common free time points of the two persons
Give the common free time slots

*/
void findCommonTimeSlots(int* per1, int size1, int* per2, int size2){
//Find all free time points for each person
const int maxTime=30;

int* free1 = new int[maxTime];
int freeSize1=0;
int* free2 = new int[maxTime];
int freeSize2=0;

//initialisation
int moment=1;
int index1=0;
while ((moment<=maxTime)&&(index1<size1)) {
if (moment==per1[index1]) //busy momment, move to check next time moment
{
moment++;
index1++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free1[freeSize1++] = moment;
//move to check next time moment
moment++;
}
}

int upper1 = per1[size1-1];
if (upper1<maxTime) //add all remaining free slots to the record
//if (per1[size1-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per1[size1-1]+1; i<=maxTime; i++)
{
free1[freeSize1++] = i;
}
}

cout << "free moments for person1 is :\n";
for (int i=0; i<freeSize1; i++)
cout << free1[i] << " ";
cout << "\n";

//initialisation
moment=1;
int index2=0;
while ((moment<=maxTime)&&(index2<size2)) {
if (moment==per2[index2]) //busy momment, move to check next time moment
{
moment++;
index2++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free2[freeSize2++] = moment;
//move to check next time moment
moment++;
}
}

if (per2[size2-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per2[size2-1]+1; i<=maxTime; i++)
{
free2[freeSize2++] = i;
}
}

cout << "free moments for person2 is :\n";
for (int i=0; i<freeSize2; i++)
cout << free2[i] << " ";
cout << "\n";


//Find those common free time points of the two persons
//reset start index for both free time record arrays
index1=0;
index2=0;
int maxfreeSize = (freeSize1>freeSize2)?freeSize1:freeSize2;
int* commonFree = new int[maxfreeSize];
int freeSize=0;

while ((index1<freeSize1)&&(index2<freeSize2))
{
if (free1[index1]==free2[index2]) //a common free moment is found
{
commonFree[freeSize++]=free1[index1];
//move to check next sample
index1++; index2++;
}
else if (free1[index1]< free2[index2])
index1++;
else //free1[index1] > free2[index2]
index2++;
}

cout << "common free moments for both persons are :\n";
for (int i=0; i<freeSize; i++)
cout << commonFree[i] << " ";
cout << "\n";


//Give the common free time slots
int startInd=0;
int endInd=startInd;
//find each common free time slot in sequence
cout << "All common free time slots are: \n";
while ((startInd<freeSize)&&(endInd<freeSize))
{
if (commonFree[endInd+1] == commonFree[endInd]+1) //continuous free slot, skip
{endInd++;}
else //a time slot is found
{
cout<< "(" << commonFree[startInd]<< "," <<commonFree[endInd]<<")\n";
startInd=endInd+1; //move to find next slot
endInd=startInd;
}
}

}

int main(){

int per1[18] = {1,2,3,4,5,10,11,12,13,14,19,20,23,24,27,28,29,30};
int per2[13] = {3,4,5,12,13,14,15,18,19,20,21,23,24};
findCommonTimeSlots(per1, 18, per2, 13);

return 0;
}

- Kevin February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
/*
Given a set of busy time intervals of two people as in a calendar, find the free time intervals of both the people so as to arrange a new meeting
input: increasing sequence of pair of numbers
per1: (1,5) (10, 14) (19,20) (23,24) (27,30)
per2: (3,5) (12,15) (18, 21) (23, 24)
ouput: (6,9) (16,17) (22,22) (25,26)

Algo:
Find all free time points for each person
Find those common free time points of the two persons
Give the common free time slots

*/
void findCommonTimeSlots(int* per1, int size1, int* per2, int size2){
//Find all free time points for each person
const int maxTime=30;

int* free1 = new int[maxTime];
int freeSize1=0;
int* free2 = new int[maxTime];
int freeSize2=0;

//initialisation
int moment=1;
int index1=0;
while ((moment<=maxTime)&&(index1<size1)) {
if (moment==per1[index1]) //busy momment, move to check next time moment
{
moment++;
index1++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free1[freeSize1++] = moment;
//move to check next time moment
moment++;
}
}

int upper1 = per1[size1-1];
if (upper1<maxTime) //add all remaining free slots to the record
//if (per1[size1-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per1[size1-1]+1; i<=maxTime; i++)
{
free1[freeSize1++] = i;
}
}

cout << "free moments for person1 is :\n";
for (int i=0; i<freeSize1; i++)
cout << free1[i] << " ";
cout << "\n";

//initialisation
moment=1;
int index2=0;
while ((moment<=maxTime)&&(index2<size2)) {
if (moment==per2[index2]) //busy momment, move to check next time moment
{
moment++;
index2++;
}
else //a free moment is found
{
//add the found free moment to record array free1
free2[freeSize2++] = moment;
//move to check next time moment
moment++;
}
}

if (per2[size2-1]<maxTime) //add all remaining free slots to the record
{
for (int i=per2[size2-1]+1; i<=maxTime; i++)
{
free2[freeSize2++] = i;
}
}

cout << "free moments for person2 is :\n";
for (int i=0; i<freeSize2; i++)
cout << free2[i] << " ";
cout << "\n";


//Find those common free time points of the two persons
//reset start index for both free time record arrays
index1=0;
index2=0;
int maxfreeSize = (freeSize1>freeSize2)?freeSize1:freeSize2;
int* commonFree = new int[maxfreeSize];
int freeSize=0;

while ((index1<freeSize1)&&(index2<freeSize2))
{
if (free1[index1]==free2[index2]) //a common free moment is found
{
commonFree[freeSize++]=free1[index1];
//move to check next sample
index1++; index2++;
}
else if (free1[index1]< free2[index2])
index1++;
else //free1[index1] > free2[index2]
index2++;
}

cout << "common free moments for both persons are :\n";
for (int i=0; i<freeSize; i++)
cout << commonFree[i] << " ";
cout << "\n";


//Give the common free time slots
int startInd=0;
int endInd=startInd;
//find each common free time slot in sequence
cout << "All common free time slots are: \n";
while ((startInd<freeSize)&&(endInd<freeSize))
{
if (commonFree[endInd+1] == commonFree[endInd]+1) //continuous free slot, skip
{endInd++;}
else //a time slot is found
{
cout<< "(" << commonFree[startInd]<< "," <<commonFree[endInd]<<")\n";
startInd=endInd+1; //move to find next slot
endInd=startInd;
}
}

}

int main(){

int per1[18] = {1,2,3,4,5,10,11,12,13,14,19,20,23,24,27,28,29,30};
int per2[13] = {3,4,5,12,13,14,15,18,19,20,21,23,24};
findCommonTimeSlots(per1, 18, per2, 13);

return 0;
}

- Kevin February 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given a list of busy times as "Pairs", I first derive the free time intervals for each person, and the check how these free times overlap. The algorithm is of linear complexity.

public class findFreeTime {
	
	public static List<Pairs> find(List<Pairs> busy1, List<Pairs> busy2){
		
		List<Pairs> output = new ArrayList<>();
		List<Pairs> free1 = freeTimes(busy1);
		List<Pairs> free2 = freeTimes(busy2);
		
		while(free1.size() != 0 && free2.size() != 0){
			Pairs overlap = doOverlap(free1.get(0), free2.get(0));
			if(overlap.start == -1 || overlap.end == -1){//checks if the pair is invalid and two pairs don't overlap
				if(free1.get(0).start < free2.get(0).start)
					free1.remove(0);
				else
					free2.remove(0);
			}
			else
				output.add(overlap);
		}
		return output;
	}
	
	//Checks if two pairs have an overlap. If they do, return the overlap. Otherwise, returns an invalid pair
	private static Pairs doOverlap(Pairs p1, Pairs p2){
		int start = -1,end = -1;
		if(p1.start >= p2.start){
			if(p1.start <= p2.end){
				start = p1.start;
				if(p1.end <= p2.end)
					end = p1.end;
				else
					end = p2.end;
			}
		}
		else{
			if(p2.start <= p1.end){
				start = p2.start;
				if(p2.end <= p1.end)
					end = p2.end;
				else
					end = p1.end;
			}
		}

		return new Pairs(start,end);
	}
	
	//Derive the free times out of busy times
	private static List<Pairs> freeTimes(List<Pairs> input){
		List<Pairs> output = new ArrayList<>();
		for(int i=0; i<input.size(); i++){
			if(i != input.size()-1){
				Pairs p = new Pairs(input.get(i).end,input.get(i+1).start);
				output.add(p);
			}
			else{
				if(input.get(i).end < 30){
					Pairs p = new Pairs(input.get(i).end+1,30);
					output.add(p);
				}
			}
		}
		return output;
	}
	
	private static class Pairs{
		int start;
		int end;
		
		public Pairs(int start, int end){
			this.end = end;
			this.start = start;
		}
	}
}

- Reyhan JB July 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

class Program
    {
        static void Main(string[] args)
        {
            List<Days> person1 = new List<Days>();
            List<Days> person2 = new List<Days>();
            List<Days> meetings = new List<Days>();
            person1.Add(new Days() { X = 1, Y = 5 });
            person1.Add(new Days() { X = 10, Y = 14 });
            person1.Add(new Days() { X = 19, Y = 20 });
            person1.Add(new Days() { X = 21, Y = 24 });
            person1.Add(new Days() { X = 27, Y = 30 });
            person2.Add(new Days() { X = 3, Y = 5 });
            person2.Add(new Days() { X = 12, Y = 15 });
            person2.Add(new Days() { X = 18, Y = 21 });
            person2.Add(new Days() { X = 23, Y = 24 });
            meetings = FindMeetingDays(person1, person2);
            foreach (Days days in meetings)
            {
                Console.WriteLine(days.X + " " + days.Y);
            }

            Console.ReadLine();

        }
        private static List<Days> FindMeetingDays(List<Days> person1, List<Days> person2)
        {
            bool[] meetings = new bool[32];
            bool[] busydays1 = new bool[32];
            bool[] busydays2 = new bool[32];
            Days days = new Days();
            List<Days> meeting_days = new List<Days>();
            busydays1 = ConvertListDays(person1);
            busydays2 = ConvertListDays(person2);
            for (byte i = 1; i < 32; i++)
            {
                meetings[i] = !busydays1[i] && !busydays2[i] ? true : false;
                if (meetings[i])
                {                   
                        if (days.X != 0) days.Y = i;
                        else days.X = i;
                }
                if(!meetings[i] && meetings[i-1])
                {
                    meeting_days.Add(days);
                    days = new Days();
                }
            }
            return meeting_days;

        }
        private static bool[] ConvertListDays(List<Days> days)
        {
            bool[] temp = new bool[32];
            foreach (Days d in days)
            {
                for (byte i = d.X; i < d.Y+1; i++)
                {
                    temp[i] = true;
                } 
            }
            return temp;
        }
    }

    struct Days
    {
        public byte X
        {
            get;
            set;
        }

        public byte Y
        {
            get;
            set;
        }

        
    }

- Eugene Mmmmm December 04, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More