Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I just realized that intervals in the input are sorted.
Thus, we can do in linear time.
My post was updated.
I've just came up with exactly same solution as you did. Let's hope it's a correct one :)
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.
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
}
}
}
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)
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));
}
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!
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.
In addition, if they were overlaping, you would not have to make a problem with 2 persons.
There will not be overlapping time as it is his meeting times, he cant be in two meetings at the same time
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!
//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)));
}
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);
}
}
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.
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;
}
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
results.add(new int[]{workingEnd, event[1]-1});
Should this be:results.add(new int[]{workingEnd, event[0]-1}); ?
lastWorkingEnd-startOfCurrentEvent-1
<?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);
$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);
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;
}
}
}
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;
}
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
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);
}
}
}
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;
}
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);
}
}
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
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;
}
}
}
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;
}
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 + ")";
}
}
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);
}
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;
}
}
}
/*
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;
}
}
}
/*
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;
}
}
}
/*
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;
}
}
}
/*
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;
}
}
}
/*
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;
}
}
}
/*
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;
}
}
}
#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;
}
#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;
}
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;
}
}
}
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;
}
}
@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:
- ninhnnsoc December 03, 2014