CareerCup

worst algorithm is n2. If you sort by start times (nlogn)
then for each app(current app), do a binary search to find the largest start time (last conflicting app) which is less than current apps end time. All the apps between current app and last conflicting app is conflicting. so nlogn+nlogn

Use an interval tree:

en.wikipedia.org/wiki/Interval_tree

red black tree with additional field start,end time. start time is used as key. each node will maintain latest end time in its sub-tree. search from root. time for search will be O(klogn), k is number of conflicting appointments.

here the point is what policy we use to define which appointments are conflicting.
there are at least two options:
1. minimize the time interval between two scheduled appointments
2. maximize the total number of scheduled appointments

I guess the last option is more "fair" in a sense that we prefer to have many short
appointments instead of just a few long ones

this problem can be solved by greedy alg in O(nlogn) time.
first sort the appointments by increasing finishing times:
suppose f[1] <= f[2] <= ... <= f[n]

then run the following alg:
A = {1} // the first appointment
j = 1;
for i = 2 to n do
if s[i] >= f[j] then
A = A + {i} // add appointment 'i'
j = 1
end if
end do

accordingly all conflicting are those that are not in A

<pre lang="" line="1" title="CodeMonkey58639" class="run-this">// The last function is the answer
import java.util.*;

public class Intervals
{
// You are given 'n' appointments. Each appointment contains starttime and endtime. You have to return all conflicting appointments efficiently starttime and endtime can range from a few min to few years.
public static class Interval implements Comparable<Interval>
{
Long start_, end_;

public Interval(long start, long end)
{
this.start_ = start;
this.end_ = end;
}

@Override
public int compareTo(Interval interval)
{
if (start_ == interval.start_)
return -end_.compareTo(interval.end_);
return start_.compareTo(interval.start_);
}

@Override
public String toString()
{
return "[" + start_ + "," + end_ + "] ";
}
}

public static void main(String[] args)
{
int n = 6;
Interval[] appointments = new Interval[n];
Random random = new Random();
for (int i = 0; i < n; i++)
{
long start = Math.abs(random.nextInt());
long end = start + Math.abs(random.nextInt());
appointments[i] = new Interval(start, end);
}
printConflicts(appointments);
}

private static void printConflicts(Interval[] appointments)
{
Arrays.sort(appointments);

Interval reference = appointments[0];
for (int i = 1; i < appointments.length; i++)
{
Interval interval = appointments[i];
if (reference.end_ > interval.start_)
System.out.println(reference + "↔ " + interval);
if (interval.end_ > reference.end_)
reference = interval;
}
}
}</pre><pre title="CodeMonkey58639" input="yes">
</pre>

Unless I am missing something, the worst case scenario is O(n^2), assuming we have to print out all the pairs of conflicting appointments. Consider this example: [(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(1,2)], where all the meetings have the exact same start and stop time. In this case, the first meeting conflicts with all the rest, the second meeting conflicts with all the rest etc. Even if the pairs of conflicting meetings are unique (i.e. (first, second)=(second,first)), there are still n(n+1)/2 pairs to print, which is O(n^2)

typedef class _Interval
{
public:
    int start;
    int end;
}Interval;

int compareIntervals(void * _start, void *_end)
{
    Interval *start = (Interval *)_start;
    Interval *ending = (Interval *)_end;

    if (start->start == ending->start)
    {
        return start->end - ending->end;
    }

    return start->start - ending->start;
}

void PrintConflicts(Interval *arr, int n)
{
    if (n == 0) return;

    qsort(arr, n, sizeof(arr[0]), compareIntervals);

    Interval *reference = arr;

    for (int i = 1; i < n; ++i)
    {
        if (reference->end < arr[i].start)
        {
            printf("start:%d end:%d conflicts", arr[i].start, arr[i].end);
        }
        else if (arr[i].end > reference->end)
        {
            reference = &arr[i];
        }
    }
}

prefix tree is the best way

We can use interval trees to represent the appointment time and while adding a new appointment to the tree we can check if there is any conflicting node and can store conflicting time in some other list.

Node will have : {start_time , end_time , node * left node * right}

I think a thread scheduling algo will work. assuming we want to schedule max number of appointments
1. Sort all appointments by their end times in increasing order.
2. take first one and it's non-conflicting
3. iterate though remaining ones now.
4. if next appointment start time is more than end time selected, this is conflicting.. add it to the conflicting list
5. else update the end time to this one.

In end we will have a list of conflicting appointments.

1. For each appointment fill a Map<Integer,List<String>> e.g. if the first appointment is 1 to 5, put following entries in a map:
1: 1-5
2: 1-5
3: 1-5
4: 1-5
5: 1-5
2. When another appointment arrives, try doing the same thing again.
3. If the map is already having a value, check if there is a conflict (because 5-6 is not conflicting with 1-5 and 5 will have a value in both the cases)

This goes through each appointment once but has to go through the mapped hours multiple times. Not sure if you can call it O(N)?

Please suggest.