CareerCup

How about bitmap approach ? 

If each slot is 30 minute, so there are 48 slots each day. In this case, long type variable (64 bits) is enough to mark meeting slots in whole day. We can use two long variable for each day. First long variable mark the start slot of one meeting, and second long variable mark the duration slot of that meeting, but keep start slot excluded since it's already marked in first long variable. 

Suppose meeting A is from slot n (n is 0-based index) and duration m slots, so

  begin_marker      = begin_marker OR (1<<n)
  duration_marker  = duration_marker  OR (( (1<<m-1)-1)<<n)

to get bitmap marker for meeting starting from slot n, 

  meeting_marker = (begin_marker  AND ~( 1<<(n+1) - 1)) 
  meeting_marker = meeting_marker OR (1<<48)   // safeguard
  meeting_marker = (meeting_marker XOR (meeting_marker - 1)) >> 1
  meeting_marker = meeting_marker XOR (1 << n - 1)
  meeting_marker = meeting_marker AND (begin_marker OR duration_marker)

to check if two meetings collide

  (meeting_marker_a AND meeting_marker_b) != 0

By this way, only array long[7][2] is required for scheduling meeting within one week

* idea only *

A very simple idea would be to use an hashset, i.e., O(1) for both insertion and lookup. Time slotting need to be predefined, or it can be hard to nadle collision between a meeting starting at 9:01 vs a meeting starting at 9. So, if we decide resolution is half an hour, meeting 9-->10 would occupy two entries in hashSet (9_930 and 930_10).
Example in java below (well, not really much to do)

// slots are represented as string "tStart_tEnd"
	private static void meetingSchedule(List<String> l ){	
		Set<String> calendar = new HashSet<String>(); 
		for (String str: l){
			if (calendar.contains(str))
				System.out.println("Meeting already scheduled"); 
			else
				calendar.add(str); 			
		}
	}

How about a heap of start times. Gives O(lg n) insert and deletes. Not as fast as a hash-map though. But you can have meeting of any width.

C++ implementation of Ankit's way

insert o(lgN)
lookup o(1)
delete o(lgN)

class Meeting
{
public:
	int start;
	int end;
	Meeting(){start = end = 0;};
	Meeting(int s, int e):start(s),end(e){};	
	bool operator < (const Meeting& o) const
	{
		return this->end < o.start;
	}
	bool operator == (const Meeting& o) const
	{
		return !(*this < o || o < *this) ;		
	}	
};

class MeetingManager
{
public:
	MeetingManager(){};
	bool AddMeeting(Meeting& m)
	{
		if(setMeeting.find(m) != setMeeting.end())
			return false;
		setMeeting.insert(m);
		mapMeetings[MeetingToKey(m)] = m;
	}

	bool GetMeeting(int start, int end, Meeting& m)
	{
		string sKey = MeetingToKey(Meeting(start,end));
		if(mapMeetings.find(sKey) == mapMeetings.end())
			return false;
		m = mapMeetings[sKey];
	}

	void DeleteMeeting(const Meeting& m)
	{
		string sKey = MeetingToKey(m);
		if(mapMeetings.find(sKey) == mapMeetings.end())
			return ;
		mapMeetings.erase(sKey);
		setMeeting.erase(m);
	}

private:
	set<Meeting> setMeeting;
	unordered_map<string, Meeting> mapMeetings;

	string MeetingToKey(const Meeting& m)
	{
		char buf[255];
		sprintf_s(buf, "%d,%d", m.start, m.end);
		string s(buf);
		return s;
	}
};

import java.io.ObjectInputStream.GetField;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;


public class MeetingSchedular {

	/**
	 * @param args
     *Design a meeting scheduler. One way is to use an array to represent each interval, 
     *like every 15 mins. Although it provides O(1) look up, if interval is small, 
     *it seems like we are wasting a lot of space. Any alternative approach that can save space? 
     *If we keep a sorted array of meetings sorted by start time, look up will be O(logn), 
     *but inserting the new meeting in the middle of the array will require shifting elements, which is O(n).
	 */
	
	Set<Meeting> meetingShedularSet=new TreeSet<Meeting>();
	Map<String,Meeting> map=new HashMap<String,Meeting>();
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MeetingSchedular ms=new MeetingSchedular();
		ms.addMeeting(new Meeting(900, 1000));
		ms.addMeeting(new Meeting(1030, 1100));
		ms.addMeeting(new Meeting(1101, 1130));
		ms.addMeeting(new Meeting(1131, 1245));
		ms.addMeeting(new Meeting(1105, 1145));
		ms.addMeeting(new Meeting(1205, 1345));
		
		Meeting meeting=ms.getMeeting(900, 1000);
		if(meeting!=null)
		{
		System.out.println("Meeting is sheduled at : "+meeting.getStartTime());
		}
		else
		{
			System.out.println("Meeting does not exist");
		}
		
		

	}
	
	public void addMeeting(Meeting meeting)
	{
		if(!meetingShedularSet.contains(meeting))
		{
		meetingShedularSet.add(meeting);
		map.put(String.valueOf(meeting.getStartTime()+meeting.getEndTime()), meeting);
		}
		else
		{
			System.out.println("Meeting with start time :"+meeting.getStartTime()+" and end time :"+meeting.getEndTime()+" is conflicting with other meeting");
		}
	}
	
	public Meeting getMeeting(int startTime,int endTime)
	{
		return map.get(String.valueOf(startTime+endTime));
	}

}


class Meeting implements Comparable<Meeting>
{
	private Integer startTime;
	private Integer endTime;
	
	
	Meeting(int startTime,int endTime)
	{
		this.startTime=startTime;
		this.endTime=endTime;
	}


	public Integer getStartTime() {
		return startTime;
	}


	public Integer getEndTime() {
		return endTime;
	}


	@Override
	public int compareTo(Meeting o) {

		if(o.getStartTime().compareTo(this.endTime)>0)
		{
			return 1;
		}
		else if(o.getEndTime().compareTo(this.startTime)<0)
		{
			return -1;
		}
		else
		{
		return 0;
		}
	}
	
	
	
	
}

package com.omtest;

import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Resource{
	Meeting m;
	Resource(Meeting m){
		this.m = m;
	}
}
class Attendee extends Resource{
	public Attendee(Meeting m) {
		super(m);
	}
}
class Room extends Resource {
	Room(Meeting m) {
		super(m);
	}
}

class Meeting {
	int id;
	String description;
	Set<Resource> attendes;
	Meeting(String description) {
		this.description = description;
		attendes= new HashSet<Resource>();
	}
}

public class SchedulerAssistant {
	private Map<Date, Map<Integer, Set<Resource>>> schedulerMap = new HashMap<>();
	
	public Map<Integer, Set<Resource>> getOverlappedResources(Set<Resource> attendees, Date date, int startTime, int duration) {
		Map<Integer,Set<Resource>> overlapMap = new HashMap<>();
		
		Map<Integer,Set<Resource>> existingMap = schedulerMap.get(date);
		for(int i = startTime; i< startTime + duration; i = i+30) {
			overlapMap.put(i, new HashSet<Resource>());
			Set<Resource> overlapResources = existingMap.get(i);
			for(Resource resource : attendees) {
				if(overlapResources.contains(resource)) {
					overlapMap.get(i).add(resource);
				}
			}
		}
		return overlapMap;
	}
	
	public boolean scheduleMeeting(Set<Resource> attendees, Date date, int startTime, int duration, String meetingDescription) {
		if(getOverlappedResources(attendees, date, startTime, duration).size() > 0) {
			return false;
		}
		Meeting m = new Meeting(meetingDescription);
		m.attendes.addAll(attendees);
		if(!schedulerMap.containsKey(date)) {
			schedulerMap.put(date, new HashMap<Integer,Set<Resource>>());
		}
		
		for(int time =startTime; time < startTime+duration; time = time + 30) {
			if(schedulerMap.get(date).containsKey(time)) {
				schedulerMap.get(date).get(startTime).addAll(attendees);
			} else {
				schedulerMap.get(date).put(time, attendees);
			}
		}
		return true;
	}
	
	public Meeting getMeeting(Date date, int time, Resource attendee) {
		Set<Resource> resources = schedulerMap.get(date).get(time);
		for(Resource res : resources) {
			if(res.equals(attendee)) {
				return res.m;
			}
		}
		return null;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

Please give me your comments so that I could correct the issues in this code.

why can't we bst