CareerCup

Here is a simpler greedy solution:
First, sort all ranges based on ENDING date in increasing order
Since dates are usually in small range we could make this step O(n) by using bucket based sorting like counting sort.
Then, from first range to last:
Select last two days (because they produce maximum possibility to overlap next range)
Skip following ranges that also contains those two days, until a range that either covers only one day (we then select last day of this range) or does not cover any of the two (we then select last two days of this range). Then continue.

I doubt that it can be done in O(n), unless we use some O(n) sorting algorithm.
I have a piece of code solving this problem, but just a rough draft. I have tested it with many cases, it should be correct.
It runs on O(n*d) time, where d is the required events numbers for each employee (here, it's 2).
Here is the data structure I use:

struct Interval;
struct TimeMark
{
	int time;
	enum TimeType{BEG, END} flag;
	Interval * owner_ptr;
	TimeMark(int t, TimeType f):time(t), flag(f), owner_ptr(nullptr) {}
	bool operator<(const TimeMark & to_less) const
	{
		return time < to_less.time || time == to_less.time && flag == BEG && to_less.flag == END ;
	}
	operator int(){
		return  time;
	}

};

struct Interval
{
	TimeMark beg_time;
	TimeMark end_time;
	typedef TimeMark::TimeType TimeType;
	int count;
	Interval(int beg_t, int end_t): beg_time(beg_t, TimeType::BEG), end_time(end_t,  TimeType::END), count(0){
		assert(end_time - beg_time >= 0);
		beg_time.owner_ptr = this;
		end_time.owner_ptr = this;
	}
	
};

Suppose we need to only find d = 1 day for each employee.
First, we sort all the beginning dates and ending dates together, with an extra condition that if the value are same, then a beginning date should be put before an ending date.

Then, we traverse this sorted dates array.
If we meet a beginning date, we push it onto a stack.
if we meet a ending date, and its corresponding beginning date is in the stack (this can be checked in O(1) by making some tag or count), we push this date into event_days(a list to store the results) and pop all the elements in the stack.
if we meet an ending date, and its corresponding beginning date is NOT in the stack, we do nothing.
return event_days.

For d > 1, we need to do the above process for d times with a small modification:.
if we meet a ending date ...... we
decrement this date by 1. // The correctness may be hard to see, but this is effective.
and push this date into results_vector and pop all the elements in the stack.

ofc, we need to resort the array at the beginning of each pass.

Here is the code:

list<int> solve(vector <Interval> intervals, int meeting_num)
{
	vector<TimeMark> timemarks;
	list<int> event_days;
	for_each(intervals.begin(), intervals.end(), [&timemarks](Interval interval){timemarks.push_back(interval.beg_time);timemarks.push_back(interval.end_time);});
	
	for (int i = 0; i < meeting_num; ++i)
	{
		sort(timemarks.begin(), timemarks.end());
		assert(timemarks[0].flag ==  TimeMark::BEG);
		stack<TimeMark> timemark_stack;
		for (auto iter = timemarks.begin(); iter < timemarks.end(); iter ++)
		{
			if (iter->flag ==  TimeMark::BEG)
			{
				timemark_stack.push(*iter);
			}else{
				if (iter->time - iter->owner_ptr->beg_time + 1< meeting_num - i)
					return list<int>();
				if (iter->owner_ptr->count == i)
				{
					while(!timemark_stack.empty())
					{
						timemark_stack.top().owner_ptr->count++;
						timemark_stack.pop();
					}
					event_days.push_back(*iter);
				
					iter->time --;
					
				}

			}
		}
	}
	
	return event_days;
}

use a min-heap to extract-min based on end times. Keep track of the last 2 scheduled times and if an interval does not intersect the 2 most recent schedules, add a new one. Select new meeting schedules based on (end) and (end-1) times of each interval to maximize likelihood of intersection with future intervals.

int schedule_meetings_twice(int size, int *starts, int*ends) {
        if(size == 0) return 0;
    
        intervalheap iheap(size);
        for(int i=0 ; i<size ; i++)
                iheap.add(new interval(starts[i], ends[i]));

        int total = 2;
        interval *iv = iheap.extract();
        int last1 = iv->end;
        int last2 = iv->end-1;
        delete iv; 

        cout << "at: " << last1 << " and " << last2 << endl;

        while(!iheap.isempty()) {
                interval *iv = iheap.extract();
                if(iv->start > last1) {
                        total+=2;
                        last1 = iv->end;
                        last2 = iv->end-1;

                        cout << "at: " << last1 << " and " << last2 << endl;
                } else if(iv->start > last2) {
                        total+=1;
                        last2 = last1;
                        last1 = iv->end;

                        cout << "at: " << last1 << endl;
                }   
                delete iv; 
        }   

        return total;
}

Get the min end time and max start time from all the employees. We have to include both these employees and all the other will have times overlapping with this time.
So, our answer would be difference of these times + 2 (to include these two employee one more day)

public int getMinDays ( int [ ] start, int [ ] end ) {

	if ( start == null || end == null ) {
		return -1;
	}
	
	int minEnd= Integer.MAX_VALUE;
	int maxStart = Integer.MIN_VALUE;

	for ( int i=0; i<start.length; i++ ) {
		if ( start[i] > maxStart )
			maxStart = start[i];
		if ( end[i] < minEnd ) 
			minEnd = end[i];
	}

	return minEnd-maxStart+2;
}

The question seems incomplete. Is there a constraint on number of people that can attend "an" event?

for all employee find maximum of minimum number of days plus one.. it will give required number of days..
pls comment on my ans..

Sort the bands using the start date
Take the 1st band as 'w'
compare 'w' with the next band. It decreases or stays the same according to the overlap with this (next) band continue with lower bands
when it becomes less than 2,stop and set those 2 dates
Take the next band as 'w' and start once again

Does the event has to happen in consecutive days?

Let us say interval of dates for employee i is (xi,yi).
Sort all xi,yi together but keep a tag whether its starting or ending.
e.g., (x1,start),(y1,start),(y2,end) and so on.
Now keep another array of counts such that count[0]=1;
and count[i]=count[i-1]+1, if ith element is a start else count[i]=count[i-1]-1;
Now, keep choosing dates by picking up dates corresponding to highest values of counts in greedy way until all employee are choosen 2 times.

Writing a sample code in python assuming days will be between 1 and 30. This can be done away with some more modification. Running time seems to be o(n*d) (n: size of input, d: number of days)

def xyz(input):
    results =[] 
    init_input = [ [x,2] for x in input] #n
    days = 30 * [0] #c
    for i in input: #n*30
        for x in range(i[0], i[1]+1):
            days[x] = days[x] + 1
    
    tot = 0;
    while(tot != len(input)):
        result = days.index(max(days)) #c
        days[result] = 0
        results.append(result)
        for i in init_input:
            if(result > i[0][0] - 1 and result < i[0][1] + 1):
                i[1] = i[1] - 1
                if(i[1] == 0):
                    for y in range(i[0][0], i[0][1]+1):
                        days[y] = days[y] - 1
                    tot = tot + 1
    
    print results
    
input = [(1,4), (2,4), (3,6), (5,8)]
xyz(input)

Thanks for explanation. However, how could you prove that this greedy method indeed gives optimum solution?

There isn't O(n) algorithm in total. But if we exclude the sorting part, there is an O(n) algorithm indeed.

Greedy algorithm.
1. sort the ranges in ascending order according to their left bound.

2. delete all ranges which satisfy that there exists at least one bound which is contained by it.
For example, range [a, b]. If there is a range [c, d], (a<=c, d<=b), then we delete [a,b], because if the solution can satisfy [c, d], it can also satisfy [a, b]

3. examine each remaining range from left right. let's say we are examining range Ri=[Ai, Bi], if we already organized at least 2 events between Ai and Bi, then we just pass this range, else we organize new event(s) as near to Bi as possible, to make 2 events in Ai and Bi.

For example, [1, 8], [5, 10], [10, 14], [14, 16]
we check [1, 8] first, and select day-7 and day-8 as the event day. then we check [5, 10], there are already 2 events, pass it. Then [10, 14], we choose day-13 and day-14, then [14, 16], there is only 1 events, we then add day-16 to it. Finished.

It's easy to prove this greedy algorithm is correct as long as no range-containing relationship.

Btw, in step 2, we can use "double-ended queue" to eliminate all [a, b] ranges in O(n)'s time. If you want to know more, please wiki this data structure, or feel free to contact me.

lionxuemao@gmail.com

This is a very nice problem. My solution :

Idea: Start with maximum possible range which effectively includes all ranges. Then start to shrink it as much as possible depending on each employee range. At the end, we will be left with 1) valid range which indicates number of days that are mutual to all employees or 2) Invalid range (start > end) which indicates failure

Here is a possible solution with O(n) running time.

1) Start with maximum possible range <min, max>. call it "result"
2) Go through each employee's availability range. call it "x"
if(result.start < x.start) {
result.start = x.start;
}
if(result.end > x.end) {
result.end = x.end;
}
if(result.start > result.end) {
// No possible date(s) found which allows all the employees to attend event
Print("Sorry, no dates found");
}
3) Return result

karmaandcoding.blogspot.com /2011/03/event-scheduling-for-n-employees-in.html

Just define a Function that accepts 2 ranges and outputs a new range. Simply run through the list of all defined ranges and you are done. I will post code shortly.

This is a program that works with O(N). But is not always optimal. It depends on the order in which the intervals are presented to it.
I have given a good explanation below as to why this is occurring and what is the right way forward to the optimal solution.

class ScheduleFolks
{
    public static class Interval {
        //Assumes begin and end inclusive
        public int begin;
        public int end;
        
        Interval() {
            begin = end = 0;
        }
        
        Interval(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }
        
        //Assumes ordering that this.begin <= B.begin
        public int overlap(Interval B) {
            if ((B.begin >= this.begin) && (B.begin <= this.end))
                return (this.end - B.begin + 1);
            return 0;
        }
        
        public String toString() {
            return ("[" + begin + "," + end + "]");
        }
    }

    static void findBestInterval(Interval A, Interval B, int overlaprequired, Interval C) {
        Interval F = (A.begin <= B.begin) ? A : B;
        Interval S = (A.begin <= B.begin) ? B : A;
        
        int o = F.overlap(S);
        if (o != 0) {
            C.begin = S.begin;
            C.end   = S.begin + overlaprequired -1;
        } else {
            // We cannot do much here.
            // There is no way we can make them all attend.
            C.begin = F.end     - overlaprequired + 1;
            C.end   = S.begin   + overlaprequired - 1;
        }
        return;
    }
    
    static void findSchedulingInterval(Interval currentInterval, Interval A, int overlaprequired) {
            if ((currentInterval.begin == 0) && (currentInterval.end == 0)) {
                // This should not be executed in the normal case.... 
                // But may be, only if we had only 1 interval to schedule.
                currentInterval.begin = A.begin;
                currentInterval.end = A.begin + overlaprequired -1;
                return;
            } else {
                Interval F = (currentInterval.begin <= A.begin) ? currentInterval : A;
                Interval S = (currentInterval.begin <= A.begin) ? A : currentInterval;
        
                int o = F.overlap(S);
                if (o != 0) {
                    if (o < overlaprequired) {
                        if (currentInterval.begin <= A.begin)
                        {
                            currentInterval.end += (overlaprequired - o);
                        } else {
                            currentInterval.begin -= (overlaprequired - o);
                        }
                    } else {
                        //Nothing required at this point. Don't alter the currentInterval
                    }
                } else {
                    //There is no overlap at all. Simply stretch the current schedule to accomodate
                    if (currentInterval.begin <= A.begin) {
                        currentInterval.end = A.begin + overlaprequired -1;
                    } else {
                        currentInterval.begin = A.end - overlaprequired + 1;
                    }
                }
            }
            return;
    }
    
    static Interval scheduleEvent(Interval[] intervals, int maxOverlap) {
        Interval r = new Interval(0,0);
        if (intervals.length == 1) {
            findSchedulingInterval(r, intervals[0], maxOverlap);
            return r;
        }
        //Get the first interval done manually
        findBestInterval(intervals[0], intervals[1], maxOverlap, r);
        
        for(int i=2; i<intervals.length; i++) {
            System.out.println("Considering " + intervals[i] + " with current interval = " + r);
            findSchedulingInterval(r, intervals[i], maxOverlap);
        }
        return r;
    }
    
    public static void printIntervals(Interval[] intervals) {
            for(int i=0; i<intervals.length; i++) System.out.println(intervals[i]);
    }
    
    public static void main(String[] args) {

        int overlaprequired = 2;
        Interval[] intervals = new Interval[4];
    
        //
        //IMPORTANT NOTE
        //
        
        //Final Result is not permutation invariant
        //Try the order of 0,2,1,3 while initializing below for a different final result.
        //The problem arises because of the overlap betweem (1,5) and (2,10)
        //The good overlap throws 3 potential intermediate candidate interval namely (2,3), (3,4) and (4,5) 
        //- all good while combining (1,5) and (2,10).
        //For subsequent couplings, (2,3) and (4,7) turns out to be a poor choice as it stretches the window from (2 to 7)
        //while (4,5) and (4,7) would have yielded us (4,5) which when coupled with (6,9) would have yielded (4,7) a the final result
        //Since we go with (2,3) pair, we get (2,7) as final result.
        
        //
        //HOW TO REACH OPTIMAL SOLUTION:
        //
        
        //Sort the entries in the increasing order of interval beginning
        //Whenever there are a lot of candidate solutions always optimize in favor of higher numbers 
        //(so that the gap between future intervals would be reduced)
        //
        intervals[2] = new Interval(4,7);
        intervals[0] = new Interval(1, 5);
        intervals[1] = new Interval(2,10);
        intervals[3] = new Interval(6,9);
        
        System.out.println("Max overlap needed = " + overlaprequired);
        System.out.println("Input Intervals :");
        printIntervals(intervals);
        System.out.println("\nOutput Interval:");
        Interval result = scheduleEvent(intervals, overlaprequired); //Change Overlap Point here
        
        System.out.println("Result interval = [" +result.begin + ", " + result.end + " ]");
    }
}