Algorithm for determining member-bound subintervals of an interval -


given list of items start , end times (e.g. start days , end days [up not including] in calendar month), minimum number of spanning intervals can constructed bounded members in 1 interval , members present in aforementioned intervals? think example make more clear (feels don't have right vocabulary describe problem):

input: [a,b,c,d,e]

a: 1,3 b: 2,4 c: 1,10 d: 5,7 e: 5,10

output:

1-2: a,c 2-3: a,b,c 3-4: b,c 4-5: c 5-7: c,d,e 7-10: c,e

if there gap i'd want know (say 4-5 wasn't covered item).

i've considered basic walks of each item , min-max considerations, bsts, , interval trees in particular kind of feel lost best approach here. thanks!

  • step 1: iterate on items, building list of entries of form { day 1, start of } , { day 3, end of }.
  • step 2: sort list day.
  • step 3: combine entries same day, giving entries { day 5, [ start d, start e ] }.

(note: since days in single month, know beforehand possible days — , there aren't many — can combine 3 of above steps 1 straightforward pass using bucket sort 31 buckets.)

  • step 4: iterate on combined entries, keeping track of items have started not yet ended, , generating desired output.

Comments

Post a Comment

Popular posts from this blog

javascript - Confirm a form & display message if form is valid with JQuery -

i'm developing django application , use javascript in order improve website. i have form , display 2 things : confirm form before submit if form submitted, display message : 'form saved' it's first time i'm using js , need make process. this code : <form class = "form" method='post' action=''> {% csrf_token %} <br></br> {{ form.as_p}} <br></br> <button type="submit">valider</button> </form> <script> $('#form').submit(function() { var c = confirm("click ok continue?"); return c; //you can return c because true or false }); </script> and if form valid , saved : <script type="text/javascript" > $(document).on('valider', 'form.form', function(form) { var $form = $(form); $.ajax({ ...
Read more

Retrieving ETA (estimated time of arrival) with Google Distance Matrix API and public transit as transport mode -

Image
is possible retrieve eta google's distancematrix api (or alternative api). fyi, eta different duration, when using public transport. following example clarify request. when leave on friday @ 8.15 i'll able catch train @ 8.30 , arrive @ 9.00 am. google says duration 30 minutes. however, when leave on saturday @ 8.15 i'll able catch first train @ 9.00 , arrive @ 9.30 am. google still says duration 30 minutes, means ignore delay. google map supports functionality there api around giving me eta instead of duration. can see, distance-matrix' response no good. clarifying question little. eta estimated time of arrival , it's clear user wants know entire duration of transport (including waiting time public transport).
Read more

ionic framework - Meteor - Error: Failed to execute 'insertBefore' on 'Node' -

i trying make dynamic list display using meteor, idea load more elements each time bottom of page reached. the html template following : <template name="contacts"> {{#contentfor "headertitle"}} <div class="bar bar-header bar-assertive"> <h1 class="title">contacts :</h1> </div> {{/contentfor}} {{#ionview}} {{#ioncontent}} <div class="list"> {{#each contacts}} <a class="item item-avatar" href="/contacts/{{_id}}"> <img src="/img/ico_client.png"> <h2>{{full_name}}</h2> <p>{{company}}</p> </a> {{/each}} </div> {{#if moreresults}} <div id="showmoreresults" style="margin-left: 25px;"> <span class="loading">loading...</span> </div> {{/if}} {{/ioncontent}} {{/ionview}} </te...
Read more