Your solution has $O(n)$ computational complexity but it doesn't implement the first fit algorithm. The thought behind your solution is to insert the items one by one in the given order (that's correct) and to insert the current item in the last bin if it fits in it or to create a new bin if the current item doesn't fit in the current bin (that's wrong).
First of all, this is not what first fit algorithm asks for. You have to insert the current item in the first used bin that it fits in and if it doesn't fit in any already used bin then you will have to use a new one. You shouldn't consider only the last used bin for the insertion, but all the existing bins, that's my point. Additionally as Discrete lizard mentions in his comment, your implementation is wrong even under the wrong perspective.
I will present the correct first fit method using two different algorithms. The first one is sub-optimal, a brute force with $O(n^2)$ computational complexity, because such an algorithm will illustrate better the first fit logic. The second algorithm is the optimal one with $O(nlogn)$ computational complexity.
Now let's consider the first algorithm. We will initially use no bin. As we read the size of each item we will just iterate from left to right over all the already used bins. If we meet a bin where the current item fits (its empty size is at least equal to the size of the current item) then we use this bin, otherwise we have to use a new bin. Note that it will be very helpfull to save the remaining size of each bin and make an update every time a new item is inserted. Bellow I implement this simple solution using C++.
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int n = 0; // Current number of items
int b = 0; // Current number of bins
vector<int> IBM; // Item->bin matching: IBM[i] = bin of i-th item
vector<list<int>> BIM; // Bin->item matching: BIM[i] = list of items in i-th bin
vector<double> RBS; // Remaining bin space: RBS[i] = remaining space of i-th bin
int main()
{
double item_size; // Current item size
while (cin >> item_size) // While there are still items put them in bins
{
bool used_bin_used = false; // Was the current item put in an already used bin?
for (int i = 0; i < b; i++) // Iterate over already used bins from left to right
{
if (RBS[i] >= item_size) // If i-th bin has enough space for the current item...
{
IBM.push_back(i); // Current item was put in i-th bin
BIM[i].push_back(n); // i-th bin contains the current item
RBS[i] -= item_size; // Decrease the available space of the i-th bin
used_bin_used = true; // The current item put in an already used bin
break; // No more search for current item
}
}
if (!used_bin_used) // If true, not new bin for current item
{
IBM.push_back(b); // Current item was put in new bin
list<int> tmp; // Helping temporary list
tmp.push_back(n);
BIM.push_back(tmp); // The new bin contains the current item
RBS.push_back(1 - item_size); // Save the remaining space of the current bin
b++; // Increased number of used bins
}
// Output current result using numbering starting from 1
cout << "Item with id = #" << n + 1 << " was put in bin with id = #" << IBM[n] + 1 << ".\n" << flush;
n++; // Increased number of items
}
// Output bin containing info
cout << n << " items were inserted in " << b << " bins.\n";
for (int i = 0; i < b; i++)
{
cout << "Bin #" << i + 1 << " contains items: ";
for (list<int>::iterator it = BIM[i].begin(); it != BIM[i].end(); it++)
{
cout << *it + 1 << ' ';
}
cout << '\n';
}
return(0);
}
Notice that the solution above follows the online fashion. For each of the $n$ items we search linerly $O(n)$ bins in the worst case, so the computational complexity of the above algorithm is $O(n^2)$.
Now let's construct a second, better algorithm. We want to improve the computational complexity of the above algorithm. We would like to reduce the time needed to find the first (leftmost) bin where the current item can fit, which required $O(n)$ time per item. To achieve this goal we can use a segment tree for maximum range queries on the remaining bin spaces. This way every time time a new item is given we can go down the segment tree and find the bin that we should use in $O(logn)$ time for each item. So the computatonal complexity of the algorithm drops down to $O(nlogn)$. We can even follow the online fashion and not require any knowledge about the value $n$, as we did in the previous implementation by doubling the size of the segment tree used every time we have an overflow. The computational complexity will remain $O(nlogn)$ which can be proved using amortized analysis. The C++ implementation of this algorithm is given bellow.
#include <iostream>
#include <vector>
#include <list>
using namespace std;
int n = 0; // Current number of items
int b = 0; // Current number of bins
vector<int> IBM; // Item->bin matching: IBM[i] = bin of i-th item
vector<list<int>> BIM; // Bin->item matching: BIM[i] = list of items in i-th bin
vector<double> RBS; // Remaining bin space: RBS[i] = remaining space of i-th bin
vector<double> A; // Vector with bin remaning sizes used by segment tree
vector<double> tree; // Vector with segment tree's values
void make_base(int L)
{
for (int i = A.size(); i < L; i++)
{
A.push_back(1); // New bins will be empty
}
for (int i = tree.size(); i < 4 * L + 5; i++)
{
tree.push_back(1); // These values will be overwritten by build
}
}
void build(int node, int start, int end)
{
if (start == end)
{
tree[node] = A[start];
}
else
{
int mid = (start + end) / 2;
build(2 * node + 1, start, mid);
build(2 * node + 2, mid + 1, end);
tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
}
}
void update(int node, int start, int end, int idx, double val)
{
if(start == end)
{
A[idx] = tree[node] = val;
}
else
{
int mid = (start + end) / 2;
if(start <= idx && idx <= mid)
{
update(2 * node + 1, start, mid, idx, val);
}
else
{
update(2 * node + 2, mid + 1, end, idx, val);
}
tree[node] = max(tree[2 * node + 1], tree[2 * node + 2]);
}
}
int query(int node, int start, int end, double val)
{
if (start == end)
{
return(start);
}
int mid = (start + end) / 2;
if (tree[2 * node + 1] >= val)
{
return(query(2 * node + 1, start, mid, val));
}
return(query(2 * node + 2, mid + 1, end, val));
}
int main()
{
double item_size; // Current item size
while (cin >> item_size) // While there are still items put them in bins
{
if (tree.empty() || tree[0] < item_size)
{
int L;
if (A.empty()) L = 1;
else L = 2 * A.size();
make_base(L);
build(0, 0, A.size() - 1);
}
int idx = query(0, 0, A.size() - 1, item_size);
if (idx < b)
{
IBM.push_back(idx); // Current item was put in idx-th bin
BIM[idx].push_back(n); // idx-th bin contains the current item
RBS[idx] -= item_size; // Decrease the free space of idx-th bin
update(0, 0, A.size() - 1, idx, RBS[idx]); // Update segment tree
}
else
{
IBM.push_back(b); // Current item was put in new bin
list<int> tmp; // Helping temporary list
tmp.push_back(n);
BIM.push_back(tmp); // The new bin contains the current item
RBS.push_back(1 - item_size); // Save the remaining space of the current bin
update(0, 0, A.size() - 1, idx, RBS[idx]); // Update segment tree
b++; // Increased number of used bins
}
// Output current result using numbering starting from 1
cout << "Item with id = #" << n + 1 << " was put in bin with id = #" << IBM[n] + 1 << ".\n" << flush;
n++; // Increased number of items
}
// Output bin containing info
cout << n << " items were inserted in " << b << " bins.\n";
for (int i = 0; i < b; i++)
{
cout << "Bin #" << i + 1 << " contains items: ";
for (list<int>::iterator it = BIM[i].begin(); it != BIM[i].end(); it++)
{
cout << *it + 1 << ' ';
}
cout << '\n';
}
return(0);
}
Finally I would like to mention that first fit is a method that doesn't minimize the number of bins used. Solving this problem optimally is NP-hard. First fit algorithm is just a method that usually provides an acceptable solution in a fast manner. It is often used in practice when speed is preffered over optimallity.
