CareerCup

@Sameer Oak The solution given by @Makarand is correct. He's building a min heap using the first (k + 1) elements. For the following input, the solution will give the correct output.

2 1 4 3
k = 1

/**
 * [1,3],[2,6],[8,12],[10,18] => [1,6],[8,18]
 * Definition for an interval.
**/
 struct Interval {
     int start;
     int end;
     Interval() : start(0), end(0) {}
     Interval(int s, int e) : start(s), end(e) {}
 };
 
bool compare(Interval a, Interval b) {
    return a.start < b.start;
}

vector<Interval> merge(vector<Interval> &A) {
    vector<Interval> result;
    vector<Interval>::iterator it;
    sort(A.begin(), A.end(), compare);
    if (A.empty()) {
        return result;
    }
    else {  
        result.push_back(*A.begin());
        for (it = (A.begin() + 1); it != A.end(); ++it) {
            if ((*it).start > result.back().end)
                result.push_back(*it);
            else
                result.back().end = max(result.back().end, (*it).end);
        }
    }    
}

We can use Binary Search (Divide & Conquer) for the solution:

#include <bits/stdc++.h>
using namespace std;

bool is_possible(int A[], int size, int B, int curr_min) {
    int students = 1, sum = 0;
    
    for (int i = 0; i < size; i++) {
        if (A[i] > curr_min)
            return false;
        if (sum + A[i] > curr_min) {
            students++;
            sum = A[i]; 
            if (students > B)
                return false;
        }
        else
            sum = sum + A[i];
    }
    return true;
}

int toffees(int A[], int size, int B) {
    long long sum = 0;
    
    if(size < B)
        return -1;
 
    for(int i = 0; i < size; i++)
        sum = sum + A[i];
        
    long long start = 0, mid = 0, end = sum;
    int result = INT_MAX;
    
    while(start <= end) {
        mid = (start + end) / 2;
        if (is_possible(A, size, B, mid)) {
            result = min(result, (int)mid);
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
    return result;
}

int main() {
	int A[] = {12, 34, 67, 90};
    	int size = sizeof(A) / sizeof(A[0]);
	cout << toffees(A, size, 2);
	return 0;
}

#include <iostream>
#include <string.h>
using namespace std;
 
int count = 0;
int cache[10];
 
bool canPass(int arr[], int n, int pos, int v) {
	count++;
	if (pos >= n)
		return true;
	if ((v <= 0) || arr[pos] == 0)
		return false;
	if (cache[v] != -1)
		return cache[pos];
 
	return cache[v] = canPass(arr, n, (pos + v), v) || canPass(arr, n, (pos + (v - 1)), (v - 1)) ||
	canPass(arr, n, (pos + (v + 1)), (v + 1));
}
 
int main() {
	int pass[] = {1,1,0,1,0,1,1,1,0,1};
	int N = sizeof(pass) / sizeof(pass[0]);
	memset(cache, -1, sizeof(cache));
	cout << canPass(pass, (N - 1), 0, 1);
	cout << endl << count;
	return 0;
}

Does kd tree also serves the purpose here?

Just exploring the idea...
1) Overlapping Intervals: Use Segment Tree or Interval Tree. Tree has to be developed using minimum interval time. It can also detect collisions.

2) Non-Overlapping Intervals: Use a BST with start time of the meeting as the key (end time can is kept as a value). To detect collisions, for an input start time, check if the end time of the floor(start time) node is less than the input start time, and check if the start time of the ceil(start time) node is greater than the input end time.