Coupon Dunia Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
You can do this by sorting by start-times as well:
var times = [[1,4],[1,9],[2,8],[3,7],[5,6],[8,10]];
function maxMeetings(arr) {
arr = arr.sort(function(a, b) { return (a[0]-b[0]); });
var results = [];
var prevStart = arr[0][0];
var prevEnd = arr[0][1];
for(var i=1; i<arr.length; i++) {
var currStart = arr[i][0];
var currEnd = arr[i][1];
// trick is to maximize the # of meetings so '<'
if(currStart < prevEnd) {
prevEnd = Math.min(prevEnd, currEnd);
} else {
results.push([prevStart, prevEnd]);
prevStart = currStart;
prevEnd = currEnd;
}
}
results.push([prevStart, prevEnd]);
return results;
}
console.log(JSON.stringify(maxMeetings(times)));
You can do this by sorting by start-times as well :
var times = [[1,4],[1,9],[2,8],[3,7],[5,6],[8,10]];
function maxMeetings(arr) {
arr = arr.sort(function(a, b) { return (a[0]-b[0]); });
var results = [];
var prevStart = arr[0][0];
var prevEnd = arr[0][1];
for(var i=1; i<arr.length; i++) {
var currStart = arr[i][0];
var currEnd = arr[i][1];
// trick is to maximize the # of meetings so '<'
if(currStart < prevEnd) {
prevEnd = Math.min(prevEnd, currEnd);
} else {
results.push([prevStart, prevEnd]);
prevStart = currStart;
prevEnd = currEnd;
}
}
results.push([prevStart, prevEnd]);
return results;
}
console.log(JSON.stringify(maxMeetings(times)));
Using Dynamic Programming, because there are 24 hours per day, set the DP size to 25
int maxParties(vector<pair<int, int>> v)
{
unordered_map<int,vector<int>> record;
for(int i=0; i<v.size(); i++)
{
record[v[i].second].push_back(v[i].first);
}
vector<int> DP(25, 0);
for(int i=1; i<=24; i++)
{
DP[i]= DP[i-1];
if (!record[i].empty())
{
for(int j=0; j<record[i].size(); j++)
DP[i]= max(DP[i], DP[record[i][j]]+1);
}
}
return DP.back();
}
And the output is 3
I think this solution[ O(n) ] is better than greedy approach [O(log n)] (because of sorting) mentioned above but has a disadvantage as it uses extra space..but greedy solution's time complexity can be improved to O(n) by using count or radix sort ..Another point to note is that extra space used in greedy solution is O(1) because of count sort but in second case it is O(n).
#include <stdio.h>
int main() {
int size,in_start = 0,in_end=0,count=0;
scanf("%d",&size);
int start[size],end[size],i=0;
for(i=0;i<size;++i){
scanf("%d%d",&start[i],&end[i]);
}
in_start = start[0];
in_end = end[0];
for(i=1;i<size;++i){
if(start[i] > in_end)
{
count++;
in_start = start[i];
in_end = end[i];
}
else if(start[i] == in_start && end[i] < in_end){
in_start = start[i];
in_end = end[i];
i=1;
count = 0;
}
}
printf("%d",count+1);
return 0;
}
Average O(n log n) runtime complexity using O(n) memory though most of that is taken by the storage of the incoming values. The actual algorithm itself would take O(1) memory.
class Event implements Comparable{
int start;
int end;
Event(int start, int end){
this.start = start;
this.end = end;
}
public int compare(Event e){
return e.end - this.end;
}
}
public static int getMaxParties(Event[] parties){
Arrays.sort(parties);
int count = 0;
int currentEnd = -1;
for(Event party : parties){
if(party.start >= currentEnd){
count++;
currentEnd = party.end;
}
}
return count;
}
would it make any difference if I first sort the list based on starting time and then on end time if start time is same. then taking the first activity always.
something like this.
int count=0;
int end=arr[1].endt;
for(i=2;i<=n;i++)
{
if(arr[i].start>=end)
{
count++;
end=arr[i].endt;
}
}
return count+1;
will it give correct result? because i gave him this solution and he said that's wrong. I couldn't figured out the test case.
please help
@ritwik_pandey:
Here's the test case that would show you why sorting on the start fails:
1 24
2 3
3 4
4 5
etc
The greedy approach by @ RecruitingForSandvineCanada and the DP approach of soneyoung are both correct, I think the DP approach based on time for this specific problem is a very clever answer.
But in general, if your intervals wouldn't be time intervals, you could also solve it using another DP approach in O(nlogn). This DP approach will be more useful when there is a benefit for choosing each interval.
Anyway, here's my code, which is a Dynamic Programming approach for this problem in general. (you could easily add benefits of each interval to the code)
//finding maximum number of non-overlaping intervals
//also could be solve Greedily
//Mehrdad AP
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;
bool cmpBasedEnd(const pair<int,int> &x,const pair<int,int>& y)
{
if (x.second!=y.second)
return x.second < y.second;
else
return x.first < y.first;
}
int maximumNonOverlapIntervals(vector< pair<int,int> > intervals)
{
int N=intervals.size();
//sorting array based on end of intervals
sort(intervals.begin(),intervals.end(),cmpBasedEnd);
vector<int> dp(N,0);
for (int i=0;i<N;i++){
int j= upper_bound(intervals.begin(),intervals.begin()+i,make_pair(100000,intervals[i].first),cmpBasedEnd) - intervals.begin();
j--;//index of nearest interval(party) which could be the previous party before i-th party
dp[i]=1;
if (j>=0 && intervals[j].second<=intervals[i].first)
dp[i]+=dp[j];
if (i>0)
dp[i] = max ( dp[i] , dp[i-1]);
}
return dp[N-1];
}
int main()
{
int N;
cin >> N;
vector< pair<int,int> > V(N);
for (int i=0;i<N;i++)
cin >> V[i].first >> V[i].second ;
cout << maximumNonOverlapIntervals(V) << endl;
return 0;
}
class Party():
def __init__(self, startTime, endTime):
self.start=startTime
self.end=endTime
def numParties(partyList):
partyList=sorted(partyList, cmp=lambda x, y: x.end-y.end)
print(map(str, partyList))
numParties=0
while len(partyList)>0:
partyList=filter(lambda x : x.start>=partyList[0].end, partyList[1:])
numParties+=1
return numParties
- Put all slots in min priority queue (using start time): NlogN
- Remove min slot from priority queue in a variable 'tempSlot
Iterate through priority queue: removing the minimum slot at a time
- If the start time of removed slot is greater than end time of 'tempSlot' then increase the counter by one and save removed slot as tempSlot.. Otherwise put the combined slot of tempSlot and removed Slot as temp Slot.
Second step is also NlogN.
Code:
public static int freeSlots(Slot[] slots) {
int freeSlots = 0;
MinPQ<Slot> pq = new MinPQ<Slot>();
for (Slot slot : slots) {
pq.insert(slot);
}
Slot tempSlot = pq.delMin();
while (!pq.isEmpty()) {
Slot tempSlot2 = pq.delMin();
if (tempSlot2.start > tempSlot.end) {
freeSlots = freeSlots + 1;
tempSlot = tempSlot2;
} else {
tempSlot = tempSlot.combine(tempSlot2);
}
}
return freeSlots;
}
static class Slot implements Comparable<Slot> {
double start;
double end;
Slot(double start, double end) {
this.start = start;
this.end = end;
}
Slot combine(Slot slot1) {
return new Slot(Math.min(start, slot1.start), Math.max(end, slot1.end));
}
@Override
public int compareTo(Slot slot1) {
if (start < slot1.start) {
return -1;
}
if (start > slot1.start) {
return 1;
}
return 0;
}
}
public static void main(String[] args) {
Slot[] lines = { new Slot(1, 9), new Slot(11, 12), new Slot(1, 4), new Slot(2, 8),
new Slot(5, 6), new Slot(3, 7), new Slot(9.5, 10) };
System.out.println(freeSlots(lines));
}
#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
pair<int,int> p[100001];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
p[i].first=a;
p[i].second=b;
}
sort(p,p+n);
int ans=0;
int max=p[0].second;
for(int i=0;i<n-1;i++)
{
if(p[i].second<p[i+1].first || max<p[i+1].first)
{
max=p[i+1].second;
ans++;
}
}
cout<<ans+1<<endl;
}
}
#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
pair<int,int> p[100001];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
p[i].first=a;
p[i].second=b;
}
sort(p,p+n);
int ans=0;
int max=p[0].second;
for(int i=0;i<n-1;i++)
{
if(p[i].second<p[i+1].first || max<p[i+1].first)
{
max=p[i+1].second;
ans++;
}
}
cout<<ans+1<<endl;
}
}
#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
pair<int,int> p[100001];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
p[i].first=a;
p[i].second=b;
}
sort(p,p+n);
int ans=0;
int max=p[0].second;
for(int i=0;i<n-1;i++)
{
if(p[i].second<p[i+1].first || max<p[i+1].first)
{
max=p[i+1].second;
ans++;
}
}
cout<<ans+1<<endl;
}
}
#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
pair<int,int> p[100001];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
p[i].first=a;
p[i].second=b;
}
sort(p,p+n);
int ans=0;
int max=p[0].second;
for(int i=0;i<n-1;i++)
{
if(p[i].second<p[i+1].first || max<p[i+1].first)
{
max=p[i+1].second;
ans++;
}
}
cout<<ans+1<<endl;
}
}
Solution:
- RecruitingForSandvineCanada August 18, 20151) Sort the intervals by END times into a collection S.
2) Remove the first (earliest end time) interval from S -> you will go to that party (count++).
3) Delete all the intervals at the head of S that intersect with the one chosen in 2) as you cannot go to these parties.
4) Go back to 2) in a looping fashion.
Why is this the correct algorithm?
Assume you have a bunch of parties to go to, we are going to prove that we should FIRST pick the one with the earliest end time.
Assume otherwise (for proof by contradiction) that it's advantageous to pick another party... fill in the details.