Monthly Archives: September 2013

Interval Partitioning Problem

Everything Under The Sun

The interval partitioning problem is described as follows:
Given a set {1, 2, …, n} of n requests, where ith request starts at time s(i) and finishes at time f(i), find the minimum number of resources needed to schedule all requests so that no two requests are assigned to the same resource at the same time. Two requests i and j can conflict in one of two ways:

  1. s(i) <= s(j) and f(i) > s(j)
  2. s(j) <= s(i) and f(j) > s(i)

Example: Given 3 requests with s(1) = 1, f(1) = 3, s(2) = 2, f(2) = 4, s(3) = 3, f(3) = 5, at least 2 resources are needed to satisfy all requests. A valid assignment of requests to resources is {1, 3} and {2}.

View original post 390 more words

Advertisements

Adventures of a Programmer: Parser Writing Peril I

De Amentiae Mundi

As menacedpromised in the last post: a description of the long path
to a well determined end.

Goal: Writing a small parser for a simple but complete language as a front-end for a for a calculator back-end. With emphasis on “complete”. A simple task one might think, a very simple one. One that could have been described in full in some book I mentioned in another post.

So in medias res, as Caesar wouldn’t have said (he spoke Greek) and of to the very beginning: The Plan. Not that I ever saw it but it is said that The Plan cometh at every beginning.
What is needed for the already briefly described…uhm…purpose, to avoid the repetition of the infamous two words, that are unbeknownst to many programmers, what does the parser need to parse? What do we need to do to enable the poor thing to do so?

View original post 1,108 more words

An Interface in Solving Quantitative Distances