CareerCup

Sub-optimal solution. Please help!

public class Solution {
    
    public int maxWeight(Interval[] intervals) {
        
        //First calculate all possible subsets
        List<List<Interval>> subsets = calculateSubsets(intervals);
        
        //Since they are sorted, find the maximum weight. If intervals
        //overlap, do not use the set.
        int maxWeight = 0;
        for(List<Interal> subset: subsets){
            if(subset.size() > 0){
                int currWeight = subset.get(0).weight;
                int currEnd = subset.get(0).end;
                boolean isCandidate = true;
                
                for(int 1 = 0; i < subset.size(); i++){
                    if(subset.get(i).start < currEnd){
                        isCandidate = false;
                        break;
                    } else {
                        currWeight += subset.get(i).weight;
                        currEnd = subset.get(i).end;
                    }
                }
        
                if(isCandidate){
                    maxWeight = Math.max(currWeight, maxWeight);
                }
            }
        }
        
        return maxWeight;
        
    }
    
    public List<List<Interval>> calculateSubsets(Interval[] intervals){
        List<List<Intervals>> subsets = new ArrayList<List<String>>();
        subsets.add(new ArrayList<Interval>());
        
        Arrays.sort(intervals, new Comparator<Interval>(){
            @Override
            public int compare(Interval i1, Interval i2){
                return i1.end < i2.end;
            }
        });
        
        for(Interval i: intervals){
            List<List<Interval>> temp = new ArrayList<List<String>>();
            for(List<Intervals> s: subsets){
                ArrayList<Interval> n = new ArrayList<Interval>(s);
                s.add(i);
                temp.add(n);
            }
            subsets.addAll(temp);
        }
        
        return subsets;
    }
}

Build trees where the heads are the overlapping first N meetings and remove them from the available list, then under each tree add all possible (non-overlapping) subtrees and traverse them all.

Other way of doing this is first sort all the meetings by start time. then parse these set of meetings from start forming hour buckets or meeting buckets goal is to find all the set of meetings that are overlapping(since only one of these can be attended). Once we have the set of meeting buckets choose the highest weight meeting from each bucket.

List <Meeting> FindFirstAvilMeets (Datetime StartTime, List <Meeting> Meetings)
{
List <Meeting> ret = new List <Meeting> ();
for each(var m in Meetings)
{
if (m.StartTime < StartTime) continue;
bool bIncl = true;
for each(var m2 in Meetings)
{
if (m2.StartTime < StartTime) continue;
if (m is m2) continue;
if (m.startTime >= m2.endTime) {bIncl = false; break; }
}
if (bIncl)
ret.Add(m);
}
return ret;
}

int gMaxWt = 0;
List <Meeting> gMaxWtSol;

void FindMaxWtSolution(int Wt, List<Meeting> Found, List<Meeting> TheRest)
{
if (TheRest.Length == 0)
if (Wt > gMaxWt)
{
gMaxWt = Wt; gMaxWtSol = Found; return;
} else
return;
DateTime StartTime = new DateTime(0);
if (Found.Length > 0) StartTime =Found[Found.Length - 1];
for each(var m in FindFirstAvilMeets(StartTime, TheRest))
{
FindMaxWtSolution(Wt+m.Weight, Found.Add(m), TheRest.Remove(m);
Found.Remove(m); TheRest.Add(m);
}
}

object Solution {

  case class Meeting(start: Long, end: Long, weight: Int) extends Ordered[Meeting] {
    def isOvelappedBy(meeting: Meeting) = {
      val (min, max) = if (this <= meeting) (this, meeting) else (meeting, this)
      (min.end > max.start && min.end < max.end) || (min.end >= max.end)
    }

    override def compare(that: Meeting) = Meeting.ordering.compare(this, that)
  }

  object Meeting {
    def parse(sc: java.util.Scanner) = Meeting(sc.next().toLong, sc.next().toLong, sc.nextInt())

    implicit val ordering: Ordering[Meeting] = Ordering.by(_.start)
  }

  def readInput(): List[Meeting] = {

    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    val meetings = collection.mutable.ListBuffer.empty[Meeting]
    for (i <- 0 until n) meetings += Meeting.parse(sc)
    meetings.toList
  }

  def schedule(meetings: List[Meeting]): Int = {
    val sorted = meetings.sorted
    

    def partitionOverlappings(meeting: Meeting, meetings: List[Meeting]): (List[Meeting], List[Meeting]) = {
      (meetings.filter(meeting.isOvelappedBy(_)), meetings.filter(!meeting.isOvelappedBy(_)))
    }

    def scheduleHelper(meetings: List[Meeting], weight: Int): Int = {
      meetings match {
        case meeting::rest => {
          val (overlappings, notOverlappings) = partitionOverlappings(meeting, meetings)
          math.max(
            scheduleHelper(notOverlappings, weight + meeting.weight),
            overlappings.map(o => scheduleHelper(rest, weight)).max
            )
        }

        case _ => weight
      }
    }

    scheduleHelper(meetings, 0)

  }

  def main(args: Array[String]) {
    val meetings = readInput
    println(schedule(meetings))
  }
}

We can sort the meetings by start time, and then, compare situations of taking the particular meeting and skipping it:

class Meeting {
	public:
		int start_;
		int end_;
		int weight_;
		Meeting(int start, int end, int weight)
		{
			start_ = start;
			end_ = end;
			weight_ = weight;
		}
		bool operator < (Meeting const &other) const
		{
			if (start_ == other.start_) {
				return end_ < other.end_;
			}
			return start_ < other.start_;
		}
};

class Result {
	public:
		int total_weight_;
		vector<Meeting> meetings_;
		bool valid_;
		Result(bool valid)
		{
			valid_ = valid;
			total_weight_ = 0;
		}
};

Result OptimalSchedule(vector<Meeting> const &meetings, vector<Result> &memo, int idx = 0)
{
	if (idx >= meetings.size() ||
		idx < 0)
	{
		return Result(true);
	}

	if (idx == 0) {
		memo.clear();
		memo.resize(meetings.size(), Result(false));
	}
	if (memo[idx].valid_) {
		return memo[idx];
	}

	int next_idx = idx + 1;
	while (next_idx < meetings.size() &&
		meetings[next_idx].start_ <= meetings[idx].end_)
	{
		++next_idx;
	}

	Result take = OptimalSchedule(meetings, memo, next_idx);
	take.total_weight_ += meetings[idx].weight_;
	take.meetings_.push_back(meetings[idx]);

	Result skip = OptimalSchedule(meetings, memo, idx + 1);

	memo[idx] = take.total_weight_ > skip.total_weight_ ? take : skip;
	return memo[idx];
}

Result OptimalSchedule(vector<Meeting> &meetings)
{
	sort(meetings.begin(), meetings.end());
	vector<Result> memo;
	return OptimalSchedule(meetings, memo);
}

/*
 *Steps: 
 * 1. Sort the intervals based on start time
 * 2. Use dynamic program to calculate weight by including current meeting and skipping current meeting
 *   Use max from above two to get weight
 *
 */
public class MaximumWeightMeeting {
	
	public static List<Meeting> getMaxWeightMeeting(List<Meeting> list ,int i, int sumOfWeights, List<Meeting> result){
		//System.out.println("weight="+sumOfWeights);
		if(i >= list.size()){
			//return sumOfWeights; // don't return 0. Return what has been calculated yet
			List<Meeting> ret = result;
			ret.add(new Meeting(0,0,sumOfWeights)); // create dummy meeting with 0 start , end and sumOfWesights as sum
			return ret;
		}
		
		int nextMeetingIndex = nextPossibleMeeting(list,i);
		List<Meeting> newResult = new ArrayList<Meeting>(result); // newresult when we attend current meeting
		newResult.add(list.get(i));
		
		// Max of (attending current meeting and call for next Possible meeting that can be attended, 
		          // skip currentMeeting and call for next meeting (i+1)
		//return Math.max(getMaxWeightMeeting(list,nextMeetingIndex,sumOfWeights+list.get(i).weight, newResult),
		//		getMaxWeightMeeting(list, i+1, sumOfWeights, result));	
		
		List<Meeting>  result1 =  getMaxWeightMeeting(list,nextMeetingIndex,sumOfWeights+list.get(i).weight, newResult);
		List<Meeting>  result2 = getMaxWeightMeeting(list, i+1, sumOfWeights, result);
		
		int sumWeight1 = result1.get(result1.size()-1).weight;
		int sumWeight2 = result2.get(result2.size()-1).weight;
		
		if(sumWeight1 > sumWeight2){
			return result1;
		}else{
			return result2;
		}
	}
	
	public static int nextPossibleMeeting(List<Meeting> list , int k){
		for(int i=k+1;i<=list.size()-1;i++){
			if(list.get(i).startTime >= list.get(k).endTime){ // find next meeting that can be attended by after kth meeting
				return i;
			}
		}
		return Integer.MAX_VALUE; // very last meeting index
	}
	
	public static void main(String[] args) {
		
		List<Meeting> list = new ArrayList<Meeting>();
		list.add(new Meeting(1,4,100));
		list.add(new Meeting(1,3,200));		
		list.add(new Meeting(4,6,150));
		list.add(new Meeting(4,6,50));
		list.add(new Meeting(2,6,10));

		// Sort Meetings by Start time
		Collections.sort(list,new MeetingComparator());
	
		for(Meeting m : list){
			System.out.println(m.toString());
		}
		
		List<Meeting> result = getMaxWeightMeeting(list,0,0 ,new ArrayList<Meeting>());
		System.out.println("Max sum of weights = " + result.get(result.size()-1).weight);
		System.out.println("Max sum Meeting Intervals : " + result.toString());

	}
	
	
}

class Meeting{
	int startTime;
	int endTime;
	int weight;
	
	Meeting(int startTime, int endTime, int weight){
		this.startTime = startTime;
		this.endTime = endTime;
		this.weight = weight;
	}
	
	public String toString(){
		return this.startTime + "," + this.endTime + "," + this.weight;
	}
}

class MeetingComparator implements Comparator<Meeting>{
	public int compare(Meeting m1, Meeting m2){
		// return the one with smaller startTime
		return (m1.startTime < m2.startTime)?-1:((m1.startTime > m2.startTime)?1:0);
	}
}

Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.

def maxWeightMeetingSchedule(meetings):
    meetings.sort(key = lambda x: x.endTime)
    maxWeight = [0] * (len(meetings) + 1)
    for k in range(1, len(maxWeight)):
        j = k - 1
        while j >= 0 and meetings[j].endTime > meetings[k - 1].startTime: 
            j = j - 1
            case1 = meetings[k - 1].weight + maxWeight[j + 1] #attend meeting k
            case2 = maxWeight[k - 1]                # not attend meeting k
            maxWeight[k] = max(case1, case2)
    return maxWeight[len(meetings)]

aonecoding - please stop publishing fake questions. You are destroying the credibility of this site.