You are not logged in. Please login at www.codechef.com to post your questions!

×

KGP14D - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM

PRE-REQUISITES:

Dynamic Programming

PROBLEM:

Given interview time lengths and departure times of trains of K(<101) candidates, find the minimum number of candidates that'll miss their trains if we optimally schedule the interviews. Any interview cannot be paused in between.

Assume that to catch a train, the interview of each candidate has to end at least 30 minutes before the departure time of the train the candidate wishes to take.

Some candidates have trains next day, so for them -1 is given as departure time. Also, since departure times are given in minutes it will be less than 24*60.

EXPLANATION:

We use dynamic programming. First we'll sort candidates according to decreasing order of departure times and start processing from last candidate in our dp. We define F(i, startTime) as the answer for candidates 1,2,...i, if we start scheduling interviews at time startTime.

Note that we'll ignore the candidates with departure time -1 as they don't contribute to answer and we can always schedule there interviews after all other interviews.

Here will be the recurrences:

//i'th candidate misses the train
//no need to schedule the interview
//because it'll lead to time wastage
F(i,startTime)= 1 + F(i-1, startTime)

//schedule the interview of i'th candidate
//if he/she doesn't miss the train
if(startTime+30+interview_time[i] <= departure_time[i])
    F(i,startTime)= min(F(i,startTime), F(i-1,startTime + interview_time[i]))

)

Complexity: O(K*24*60) worst case.

IMPLEMENTATION:

See editorialist's detailed solution for implementation details.

SOLUTIONS:

Editorialist's solution

This question is marked "community wiki".

asked 25 Dec '14, 00:07

darkshadows's gravatar image

5★darkshadows ♦
3.0k93163187
accept rate: 12%

edited 25 Dec '14, 14:33


F(i,startTime)= min(F(i,startTime), startTime + interview_time[i])

should be

F(i,startTime)= min(F(i,startTime), F(i-1, startTime + interview_time[i]))

link

answered 25 Dec '14, 12:04

bbackspace's gravatar image

4★bbackspace
9614
accept rate: 6%

There's a greedy solution for this. Sort the input according to departure time of the candidate. Then iterate the array maintaining the total time consumed. Every time a candidate who can decrease the total time till now will replace the candidate selected till now consuming the highest. Else the current candidate will not be included. My solution: here.

link

answered 26 Dec '14, 03:07

anan109432's gravatar image

3★anan109432
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,477
×2,556
×2,085
×20

question asked: 25 Dec '14, 00:07

question was seen: 3,660 times

last updated: 26 Dec '14, 03:07